Zgadnij liczbę
Komputer wymyślił liczbę od 1 do 1000. Ile prób potrzebujesz? Jest sposób, który zawsze wystarcza na 10 prób. Nazywa się wyszukiwanie binarne i używają go programy, bazy danych i Ty, gdy szukasz słowa w słowniku.
Ty zgadujesz
Wpisz pierwszą liczbę. Dobry początek to środek zakresu.
Teraz komputer zgaduje
Pomyśl liczbę od 1 do 1000 (możesz zapisać ją na kartce). Komputer zawsze pyta o środek tego, co zostało. Odpowiadaj uczciwie, a zgadnie w najwyżej 10 pytaniach.
Wyścig: po kolei czy na pół?
Masz posortowaną listę 64 liczb i szukasz jednej z nich. Wyszukiwanie liniowe sprawdza po kolei od początku. Wyszukiwanie binarne patrzy na środek i odrzuca połowę, która na pewno nie zawiera szukanej liczby.
| Elementów (kroki w najgorszym razie) | liniowe | binarne |
|---|
Słownik zwierząt
Tak samo szukasz słowa w słowniku: otwierasz w środku i sprawdzasz, czy słowo jest wcześniej, czy dalej w alfabecie. Wpisz zwierzę i patrz, jak komputer zawęża poszukiwania. Potem pomieszaj słownik i spróbuj jeszcze raz.
Każde pytanie podwaja moc
Każda odpowiedź „mniejsza / większa” dzieli możliwości na pół. Z drugiej strony: każde dodatkowe pytanie pozwala zgadnąć dwa razy więcej liczb. To potęgi dwójki, te same co w bitach.
Sprawdź się
Punkty 0 · Seria 0 · Rekord 0Czym jest wyszukiwanie binarne?
Wyszukiwanie binarne (połówkowe) to sposób szukania w posortowanych danych. Sprawdzasz element w środku. Jeśli to nie ten, wiesz, w której połowie szukać dalej, a drugą połowę odrzucasz. Powtarzasz, aż znajdziesz element albo zostanie pusty przedział.
Każdy krok zmniejsza liczbę możliwości o połowę, więc dla n elementów wystarczy ok. log₂ n kroków: 10 dla tysiąca, 20 dla miliona, 30 dla miliarda. Wyszukiwanie liniowe, które sprawdza po kolei, potrzebuje w najgorszym razie aż n kroków. Haczyk: dane muszą być posortowane. Dlatego sortowanie i wyszukiwanie idą w parze.
Algorytm krok po kroku
1. Ustaw lewy koniec na początek, prawy na koniec listy. 2. Weź element w środku. 3. Jeśli to szukany, koniec. 4. Jeśli szukany jest mniejszy, przesuń prawy koniec przed środek; jeśli większy, lewy koniec za środek. 5. Wróć do kroku 2, dopóki lewy koniec nie minie prawego.
Historia w pigułce
- 1946John Mauchly opisuje wyszukiwanie binarne w wykładach o pierwszych komputerach elektronicznych.
- 1960Pojawiają się wersje działające dla dowolnej liczby elementów, nie tylko 2ⁿ − 1.
- 1986Jon Bentley pisze, że większość zawodowych programistów, których poprosił o napisanie wyszukiwania binarnego, popełniła błąd.
- 2006Joshua Bloch z Google opisuje błąd przepełnienia przy liczeniu środka (lewy + prawy) / 2, który latami siedział m.in. w bibliotece Javy.
Najczęstsze pytania o wyszukiwanie binarne
Na czym polega wyszukiwanie binarne?
Na sprawdzaniu elementu w środku posortowanej listy i odrzucaniu połowy, w której szukany element na pewno nie jest. Każdy krok zmniejsza obszar poszukiwań o połowę.
Ile prób potrzeba, żeby zgadnąć liczbę od 1 do 1000?
Najwyżej 10, jeśli za każdym razem pytasz o środek tego, co zostało. 2¹⁰ = 1024, więc 10 odpowiedzi „mniejsza / większa” wystarcza na ponad tysiąc liczb.
Czy wyszukiwanie binarne działa na nieposortowanych danych?
Nie. Bez sortowania nie wiadomo, w której połowie szukać, więc algorytm może przegapić element, który jest na liście. Najpierw trzeba posortować dane.
Czym różni się wyszukiwanie liniowe od binarnego?
Liniowe sprawdza elementy po kolei i działa na dowolnych danych, ale dla miliona elementów może potrzebować miliona kroków. Binarne wymaga posortowanych danych, ale dla miliona elementów wystarcza mu 20 kroków.
Co oznacza złożoność O(log n)?
Że liczba kroków rośnie bardzo wolno: gdy danych jest dwa razy więcej, potrzeba tylko jednego kroku więcej. Tak działa wyszukiwanie binarne.
Gdzie używa się wyszukiwania binarnego?
W bazach danych i indeksach, w słownikach i spisach, w grach (np. „za dużo / za mało”), przy szukaniu błędu w historii zmian programu (git bisect) i w wielu bibliotekach programistycznych.