Wyszukiwanie binarne

26.11.2009 - Marcin Oczeretko

Cała skuteczność wyszukiwania binarnego budowana jest na tym, że zamiast przeglądać wszystkie elementy posortowanego zbioru po kolei, sprytnie wykorzystujemy informację o tym, że jest on uporządkowany. Patrzymy więc na jego środkowy element (nazwijmy go S) i jeśli:

S jest tym czego szukamy - super! dalej już nie musimy szukać,

S jest większy niż to, czego szukamy - wszystkie elementy większe niż S są też na pewno większe niż poszukiwana wartość, możemy więc całkowicie zapomnieć o istnieniu tej części zbioru,

S jest mniejszy niż to, czego szukamy - analogocznie jak w poprzednim przypadku, możemy odrzucić wszystkie elementy mniejsze niż poszukiwana wartość.

Spójrzmy może, jak za pomocą wyszukiwania binarnego szukać $13$ w ciągu:

$\textbf{1, 2, 4, 7, 9, 11, 12, 13, 18, 27, 30, 31, 10000}$ .

Patrzymy na wartość jego środkowego elementu - jest to 12. Odrzucamy więc ten element i wszystkie go poprzedzające. Zostaje nam ciąg:

$\textbf{13, 18, 27, 30, 31, 100000}$

Ma on $6$ elementów, możemy więc sprawdzić wartość na $3$ lub $4$ pozycji (obie równie dobrze dzielą ten zbiór). Spójrzmy zatem na pozycję $4$ - jest tam $30$ . Odrzucamy wszystkie elementy od pozycji $4$ w górę, ponieważ szukamy $13$ , a $13 < 30$ . Przedział, w którym szukamy skurczył się już do: