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)
średni Θ(log n)
najgorszy O(log n)
pamięć O(1)

Co to znaczy?

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.
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ń.

środek (mid)
znalezione
odrzucone
cel

0 / 14 kroków

Każdy środek, jaki wyszukiwanie mogło wybrać; przebieg to jedna ścieżka w dół. Poziomy: 5 = ⌈log₂(24 + 1)⌉, czyli najwięcej porównań, jakie może potrzebować.

Szybkość 8 kroków/s

Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.

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.