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](https://wikimedia.org/api/rest_v1/media/math/render/svg/a30c89172e5b88edbd45d3e2772c7f5e562e5173)
![\log _{2}1/\varepsilon](https://wikimedia.org/api/rest_v1/media/math/render/svg/721f641bab10f7d5d4ad19443f420459d3c9f78b)
![{\displaystyle 1+\log _{2}N}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93810dfe31a1304cacfdf94c5a3e0f68c9ed4247)
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 .
Odkazy