Wyszukiwanie binarne
Wyszukiwanie binarne to sposób, w jaki szukasz słowa w słowniku: otwierasz go na środku, sprawdzasz, czy słowo jest wcześniej, czy dalej, i powtarzasz z tą połową. Na posortowanej liście znajduje dowolną wartość spośród miliona w najwyżej 20 porównaniach.
Idea
Na posortowanej liście jedno porównanie mówi więcej niż to, czy znaleziono szukaną wartość: mówi, po której stronie ona jest. Porównaj szukaną wartość z wartością w środku. Jeśli są równe, gotowe. Jeśli środkowa wartość jest mniejsza, wszystko przed nią też jest mniejsze, więc szukana może być tylko za nią. Jeśli jest większa, szukana może być tylko przed nią. Zostaw tylko tę połowę i powtórz.
Przykład
Szukaj 23 na liście 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Środkowa wartość to 16, jest mniejsza, więc zostają tylko wartości od 23 do 91. Ich środek to 56, jest większy, więc zostają tylko 23 i 38. Ich środek to 23: znaleziono na miejscu 6 po 3 porównaniach, a wyszukiwanie liniowe potrzebuje 6. Szukanie 40 na tej samej liście porównuje 16, 56, 23 i 38, po czym nic nie zostaje: 4 porównania, by wiedzieć, że 40 brakuje, wobec 10 przy wyszukiwaniu liniowym.
Połowienie działa szybko
Po jednym porównaniu zostaje najwyżej połowa listy, po dwóch ćwierć, po k najwyżej około n/2ᵏ. Wyszukiwanie kończy się, gdy nic nie zostanie, więc potrzebuje najwyżej ⌊log₂ n⌋ + 1 porównań: 6 dla 40 wartości, 10 dla 1000, 20 dla miliona i 30 dla miliarda. Podwojenie listy dodaje tylko jedno porównanie. Zapisuje się to jako O(log n).
Łatwe do opisania, trudne do zrobienia dobrze
John Mauchly opisał wyszukiwanie binarne w 1946 roku, ale jak podaje Donald Knuth, pierwszą wersję działającą dla każdej długości listy opublikowano dopiero w 1962. Jon Bentley odkrył później, że tylko mniej więcej jeden na dziesięciu zawodowych programistów pisał je poprawnie: warunki końca i plus lub minus jeden przy dzieleniu połówek łatwo pomylić. W 2006 roku Joshua Bloch pokazał, że popularny sposób wyznaczania środka, (low + high) / 2, może powodować przepełnienie (overflow) dla bardzo długich list, a ten błąd przez lata tkwił w bibliotece języka Java. Zapis low + (high − low) / 2, użyty w aplikacji, go unika.
Odmiany i zastosowania
Przy duplikatach wyszukiwanie binarne znajduje jedno z trafień; wersje, które idą dalej w lewo lub w prawo, znajdują pierwsze lub ostatnie albo miejsce, w które należałoby wstawić brakującą wartość. Ta sama idea połowienia znajduje pierwiastek równania (bisekcja), wersję, w której błąd pojawił się po raz pierwszy (git bisect), i odpowiedź w wielu zagadkach optymalizacyjnych. Binarne drzewa wyszukiwań przechowują dane tak, by każde wyszukiwanie szło tą samą ścieżką połowienia.
Sprawdź w praktyce
Otwórz aplikację, wybierz wartość w polu Szukaj i naciśnij Krok. Zacieniony obszar to miejsce, gdzie szukana wartość może jeszcze być; środkowa wartość jest wyróżniona, a wykluczona połowa blednie. Kafelki pokazują, ile wartości jest nadal możliwych i ile porównań potrzebowałoby wyszukiwanie liniowe dla tej samej wartości. Szukaj brakującej wartości albo użyj 40 słupków, aby zobaczyć, jak różnica rośnie.
Często zadawane pytania
Jaka jest złożoność czasowa wyszukiwania binarnego?
O(log n): najwyżej ⌊log₂ n⌋ + 1 porównań dla n wartości. W najlepszym przypadku wystarczy jedno porównanie, gdy szukana wartość jest w środku. Wersja iteracyjna potrzebuje O(1) dodatkowej pamięci.
Czym różni się wyszukiwanie binarne od liniowego?
Wyszukiwanie liniowe sprawdza po kolei każdą wartość i działa na każdej liście, ale może potrzebować n porównań. Wyszukiwanie binarne działa tylko na posortowanej liście, ale każde porównanie wyklucza połowę tego, co zostało, więc potrzebuje około log₂ n.
Czy warto sortować listę tylko po to, by użyć wyszukiwania binarnego?
Tylko jeśli przeszukujesz ją wiele razy. Sortowanie zajmuje około n log n kroków, więcej niż jedno wyszukiwanie liniowe. Gdy lista jest już posortowana, każde kolejne wyszukiwanie jest bardzo tanie.
Czy wyszukiwanie binarne działa nie tylko na listach?
Tak, na wszystkim, gdzie test mówi, po której stronie odpowiedzi jesteś: na przedziale liczb, wersjach programu czy strzałach w grze „więcej–mniej”.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj wyszukiwanie binarne