Binární vyhledávání

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. března 2021; kontroly vyžadují 29 úprav .

Binární (binární) vyhledávání (také známé jako metoda bisekce nebo dichotomie ) je klasický algoritmus pro nalezení prvku v seřazeném poli (vektoru), který využívá rozdělení pole na poloviny. Používá se v informatice , výpočetní matematice a matematickém programování .

Speciálním případem binárního vyhledávání je metoda bisekce , která se používá k nalezení kořenů dané spojité funkce na daném intervalu.

Hledání prvku v seřazeném poli

Určení hodnoty prvku uprostřed datové struktury. Výsledná hodnota je porovnána s klíčem.
Pokud je klíč menší než střední hodnota, vyhledávání se provádí v první polovině prvků, jinak - ve druhé.
Hledání se redukuje na to, že se opět určí hodnota prostředního prvku ve zvolené polovině a porovná se s klíčem.
Proces pokračuje, dokud není nalezen prvek s hodnotou klíče nebo dokud není interval hledání prázdný.

Přestože je kód poměrně jednoduchý, má několik úskalí.

Kód (first + last) / 2je chybný, pokud firsta lastjednotlivě zapadá do jejich typu, ale first+last ne [1] . Pokud jsou pole tak velké velikosti teoreticky možná, musíme se uchýlit k trikům:
- first + (last - first) / 2Při práci s nezápornými celými čísly a první<poslední použijte kód , který rozhodně nepovede k přetečení.
  - Pokud firsta last jsou ukazatele nebo iterátory , je takový kód jediný správný, protože neporušuje abstrakci (operace „ukazatel + ukazatel“ je již nesprávná). Samozřejmě, abychom zachovali složitost algoritmu, potřebujeme rychlé operace „ukazatel+číslo → ukazatel“, „ukazatel–ukazatel → číslo“.
- Pokud firsta last jsou podepsané typy, proveďte výpočet v nepodepsaném typu: ((unsigned)first + (unsigned)last) / 2. V Javě bude fungovat následující kód: (first + last) >>> 1(podepsané binární sčítání je stejné jako nepodepsané, Java toto chování zaručuje i při přetečení a celý tento vzorec funguje na podepsaných číslech jako nepodepsaný).
- Napište výpočet v assembleru pomocí carry flag . Něco jako add eax, b; rcr eax, 1. Není však vhodné používat dlouhé typyfirst + (last - first) / 2 , je to rychlejší.
Chyby po jedné jsou běžné v binárním vyhledávání a každá taková chyba se změní na smyčku , přeskočení nebo pole mimo hranice. Proto je důležité otestovat takové případy: prázdné pole ( n=0), jeden prvek ( n=1), hledání chybějící hodnoty (příliš velká, příliš malá a někde uprostřed), hledání prvního a posledního prvku.
Někdy je vyžadováno, aby, pokud xje v řetězci několik instancí, nebyla nalezena žádná, ale nutně první (jako možnost: poslední; nebo vůbec ne x, ale prvek, který za ní následuje). [2] Například funkce C++ najde první z rovných a najde prvek následující za x. Pokud je nenaleznete, oba vrátí místo, kam vložit.std::lower_boundstd::upper_bound

Vědec Jon Bentley tvrdí, že 90 % studentů při vývoji binárního vyhledávání zapomene vzít v úvahu některý z těchto požadavků. A i do kódu, který napsal sám Jon a přecházel z knihy do knihy, se vloudila chyba: kód není odolný vůči přetečení [1] .

Příklad implementace Java

int binarySearch ( int [] arr , klíč int ) { int low = 0 ; int high = arr . délka - 1 ; while ( low <= high ) { int mid = ( low + high ) >>> 1 ; int midVal = arr [ mid ] ; if ( midVal < klíč ) nízká = střední + 1 ; else if ( midVal > key ) vysoký = střední - 1 ; jiný návrat uprostřed ; // klíč nalezen } návrat - ( nízké + 1 ); // klíč nenalezen. }

Aplikace

Praktické aplikace metody binárního vyhledávání jsou různé:

Rozšířený v informatice ve vztahu k vyhledávání v datových strukturách. Například vyhledávání v datových polích se provádí pomocí klíče přiřazeného každému z prvků pole (v nejjednodušším případě je klíčem samotný prvek).
Používá se také jako numerická metoda pro hledání přibližného řešení rovnic (viz metoda Bisection ).
Metoda se používá k nalezení extrému účelové funkce a v tomto případě se jedná o podmíněnou jednorozměrnou optimalizační metodu . Když má funkce skutečný argument, je možné najít řešení až do času . Když je argument diskrétní a zpočátku leží na segmentu délky N , bude hledání řešení nějakou dobu trvat . Nakonec, abychom hledali extrém, řekněme pro jistotu minima , v dalším kroku se zahodí jeden z konců uvažovaného segmentu, jehož hodnota je maximum. $\varepsilon$ $\log _{2}1/\varepsilon$ $1+\log _{2}N$

Viz také

Poznámky

↑ 1 2 Extra, Extra – Přečtěte si o tom vše: Téměř všechna binární vyhledávání a slučování jsou rozbitá Archivováno 2. prosince 2013 na Wayback Machine // Joshua Bloch, Google Research; překlad — Téměř všechny implementace binárního vyhledávání a řazení mají chybu Archivováno 24. listopadu 2013 na Wayback Machine
↑ V C++ std::lower_bound najde první výskyt xa najde std::upper_bound prvek následující x.

Literatura

Levitin A. V. Kapitola 4. Metoda rozkladu: Binární vyhledávání // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 180-183. — 576 s. — ISBN 978-5-8459-0987-9
Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Výpočtové metody pro inženýry. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerické metody. - 8. vyd. - M . : Laboratoř základních znalostí, 2000.
Wirth N. Algoritmy + datové struktury = programy . - M .: " Mir ", 1985. - S. 28 .
Volkov E. A. Numerické metody. — M .: Fizmatlit, 2003.
Gill F., Murray W., Wright M. Praktická optimalizace. Za. z angličtiny. — M .: Mir, 1985.
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
Korn G., Korn T. Příručka matematiky pro vědce a inženýry. - M .: Nauka, 1970. - S. 575-576.
Korshunov Yu.M., Korshunov Yu.M. Matematické základy kybernetiky. - Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmy pro řešení problémů nelineárního programování. — M. : MEPhI, 1982.
Robert Sedgwick. Základní algoritmy v C. Základy/Datové struktury/Řazení/Vyhledávání. - Petrohrad. : DiaSoftYUP, 2003. - S. 672. - ISBN 5-93772-081-4 .