Wyszukiwanie binarne
Znajduje wartość w posortowanej tablicy: patrzy na środek i odrzuca połowę, w której jej być nie może. Każde porównanie zmniejsza to, co zostało, o połowę.
- najlepszy Ω(1)
- Θ(log n)
- najgorszy O(log n)
- pamięć O(1)
log₂ n: ile razy można podzielić n na pół, zanim zostanie 1. Dla 64 wartości to 6, więc najwyżej 7 porównań.
Inne pojęcia na tej stronie
- Posortowane: ułożone rosnąco. Wyszukiwanie binarne tego wymaga; na nieposortowanych danych daje złe wyniki.
- Połowienie: każde porównanie odrzuca połowę tego, co zostało, tę, w której celu być nie może.
- środek (mid)
- znalezione
- odrzucone
- cel
Spróbuj: Wybierz cel, którego nie ma w tablicy. Wyszukiwanie i tak skończy się po najwyżej ⌈log₂(n + 1)⌉ porównaniach, gdy lo minie hi.
Jak to działa
Wyszukiwanie binarne trzyma dwa znaczniki, lo i hi, wokół części tablicy, w której cel jeszcze może być. Patrzy na wartość w środku: jeśli to cel, koniec; jeśli jest mniejsza, cel może być tylko na prawo, więc lo przesuwa się za środek; jeśli większa, hi przesuwa się przed środek. Każdy krok zmniejsza resztę o połowę, więc 64 wartości wymagają najwyżej 7 porównań, a milion najwyżej 20. Gdy lo minie hi, nic nie zostaje: wartości nie ma w tablicy.
Kiedy warto go użyć
Wyszukiwania binarnego używa się zawsze, gdy dane są posortowane i można skoczyć do dowolnej pozycji: słowo na posortowanej liście, wersja w historii wydań, git bisect, miejsce do wstawienia w posortowanej tablicy. Na nieposortowanych danych daje złe wyniki, a sortowanie przed szukaniem opłaca się dopiero przy wielu wyszukiwaniach.