Binárne vyhľadávanie
Nájde hodnotu v zoradenom poli tak, že sa pozrie do stredu a zahodí polovicu, v ktorej byť nemôže. Každé porovnanie zvyšok zmenší na polovicu.
- najlepší Ω(1)
- priemerný Θ(log n)
- najhorší O(log n)
- pamäť O(1)
Čo to znamená?
- Zoradené: vzostupne usporiadané. Binárne vyhľadávanie to potrebuje; na nezoradených dátach dáva zlé odpovede.
- Polenie: každé porovnanie zahodí polovicu zvyšku, tú, v ktorej cieľ byť nemôže.
- log₂ n: koľkokrát sa dá n rozpoliť, kým zostane 1. Pre 64 hodnôt je to 6, teda najviac 7 porovnaní.
- stred (mid)
- nájdené
- vylúčené
- cieľ
Každý stred, ktorý by hľadanie mohlo zvoliť; beh je jedna cesta nadol. Úrovne: 5 = ⌈log₂(24 + 1)⌉, najviac porovnaní, koľko môže potrebovať.
Hľadám 70 medzi zoradenými hodnotami (n = 24): v hre je ešte celé pole.
Medzerník: prehrať alebo pozastaviť. Šípky vľavo/vpravo: krok. Home a End: preskočiť.
Skúste: Vyberte cieľ, ktorý v poli nie je. Hľadanie aj tak skončí najviac po ⌈log₂(n + 1)⌉ porovnaniach, keď lo predbehne hi.
Ako to funguje
Binárne vyhľadávanie drží dve značky, lo a hi, okolo časti poľa, kde ešte môže byť cieľ. Pozrie sa na hodnotu v strede: ak je to cieľ, koniec; ak je menšia, cieľ môže byť len vpravo, takže lo sa posunie za stred; ak je väčšia, hi sa posunie pred neho. Každý krok zvyšok polí: 64 hodnôt potrebuje najviac 7 porovnaní a milión najviac 20. Keď lo predbehne hi, nič nezostáva: hodnota v poli nie je.
Kedy sa hodí
Binárne vyhľadávanie použite vždy, keď sú dáta zoradené a dá sa skočiť na ľubovoľnú pozíciu: slovo v zoradenom zozname, verzia v histórii vydaní, git bisect, miesto na vloženie do zoradeného poľa. Na nezoradených dátach dáva zlé odpovede a zoradiť vopred sa oplatí až pri mnohých hľadaniach.