Wyszukiwanie binarne — algorytm, złożoność czasowa i kod

Wyszukiwanie binarne to szybki sposób znajdowania szukanej wartości na posortowanej liście. Sprawdzasz element środkowy, odrzucasz połowę pozostałych wartości i powtarzasz ten proces. Jeśli lista nie jest uporządkowana, ta logika nie działa.

Na liście rosnącej zasada jest prosta: jeśli wartość środkowa jest mniejsza od szukanej, szukaj po prawej stronie; jeśli jest większa, szukaj po lewej. Ponieważ zakres za każdym razem zmniejsza się mniej więcej o połowę, wyszukiwanie binarne działa w czasie $O(\log n)$.

Jak działa wyszukiwanie binarne na posortowanej liście

Użyj tej posortowanej listy:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Załóżmy, że szukana wartość to $31$.

Zacznij od całego zakresu. Wartość środkowa to $24$. Ponieważ $31 > 24$, wszystko na lewo od $24$ można odrzucić, więc wyszukiwanie jest kontynuowane w

$$[31, 39, 45, 52]$$

Teraz wartość środkowa to $39$. Ponieważ $31 < 39$, wszystko na prawo od $39$ można odrzucić, więc zakres staje się

$$[31]$$

Teraz wartość środkowa to $31$, więc wyszukiwanie się kończy. Ważna idea nie polega tylko na tym, że znaleziono szukaną wartość. W dwóch porównaniach zakres kandydatów zmniejszył się z $9$ wartości do $1$.

Dlaczego wyszukiwanie binarne ma złożoność $O(\log n)$

Każde porównanie usuwa około połowy pozostałych kandydatów. Po jednym kroku zostaje około $n/2$ elementów. Po dwóch krokach zostaje około $n/4$ elementów. Po $k$ krokach pozostały rozmiar wynosi około

$$\frac{n}{2^k}$$

Wyszukiwanie kończy się, gdy ta wartość wynosi około $1$, więc liczba kroków spełnia zależność

$$2^k \approx n$$

Po wzięciu $\log_2$ z obu stron otrzymujemy

$$k \approx \log_2 n$$

Dlatego wyszukiwanie binarne dobrze się skaluje. Wyszukiwanie liniowe może wymagać nawet $n$ sprawdzeń, ale wyszukiwanie binarne potrzebuje tylko tylu sprawdzeń, ile potrzeba, by wciąż dzielić zakres na pół.

Przykład kodu wyszukiwania binarnego

Oto standardowa wersja iteracyjna w Pythonie: