Wyszukiwanie binarne

Wyszukiwanie binarne jest wydajnym algorytmem znajdowania elementu z uporządkowanej listy elementów. Działa on poprzez wielokrotne dzielenie na pół fragmentu listy, który może zawierać szukany element, dopóki nie ograniczy jej tylko do jednej pozycji. Użyliśmy wyszukiwania binarnego w zgadywanie liczb w samouczku wprowadzającym.

Jednym z najczęstszych sposobów wykorzystania wyszukiwania binarnego jest znalezienie elementu w tablicy. Przykładowo, katalog gwiazd Tycho-2 zawiera informacje na temat jasności 2 539 913 gwiazd w naszej galaktyce. Załóżmy, że chcesz przeszukać ten katalog w poszukiwaniu konkretnej gwiazdy, na podstawie nazwy gwiazdy. Jeżeli program ten miałby zbadać każdą gwiazdę w katalogu począwszy od pierwszej, korzystając z algorytmu o nazwie wyszukiwanie liniowe, komputer w najgorszym wypadku musiałby zbadać wszystkie 2 539 913 gwiazd, aby znaleźć gwiazdę, której szukasz. Jeżeli katalog ten byłby posortowany alfabetycznie po nazwie gwiazdy, algorytm wyszukiwania binarnego nie musiałby zbadać więcej niż 22 gwiazdy, nawet w najgorszym wypadku.

Następne kilka artykułów omawia jak dokładnie opisać ten algorytm, jak go zaimplementować w JavaScript oraz jak analizować jego wydajność.

Opisując wybrany algorytm drugiemu człowiekowi, często niekompletny opis jest wystarczający. Z przepisu na ciasto możemy wykluczyć niektóre czynności, gdyż zakłada on, że wiesz jak otworzyć lodówkę, aby wyjąć z niej jajka i wiesz jak je później rozbić. Ludzie mogą intuicyjnie uzupełnić brakujące informacje, ale programy komputerowe nie i dlatego musimy szczegółowo opisywać algorytmy komputerowe.

W celu realizacji algorytmu w języku programowania, należy zrozumieć każdy szczegół tego algorytmu. Jakie mamy dane wejściowe dotyczące problemu? Jakie mamy dane wyjściowe? Jakie zmienne powinny zostać stworzone oraz jakie wartości początkowe powinny one posiadać? Jakie kroki pośrednie powinny zostać podjęte w celu obliczenia innych wartości oraz ostatecznie obliczenia wyniku końcowego? Czy te kroki powtarzają instrukcje, które mogą być zapisane w uproszczonej formie za pomocą pętli?

Przyjrzyjmy się, jak dokładnie możemy opisać wyszukiwanie binarne. Główną ideą wyszukiwania binarnego jest zawężanie aktualnego zakresu możliwych odpowiedzi. Powiedzmy, że myślę o liczbie pomiędzy 1 a 100, dokładnie jak w grze w zgadywanie liczb. Jeżeli podczas pierwszej próby podałeś liczbę 25, a ja powiedziałem, że moja liczba jest wyższa, podczas drugiej próby podałeś liczbę 81, a ja powiedziałem, że moja liczba jest niższa, wówczas liczby w zakresie pomiędzy 26 a 80 mogą być twoją jedyną kolejną możliwą odpowiedzią. Poniżej, czerwony odcinek zawiera liczby, z których można dokonać kolejnej próby, natomiast czarny odcinek zawiera liczby, które możemy wykluczyć.

W każdej turze wybierasz liczbę, która dzieli zakres możliwych odpowiedzi na dwie mniej więcej równe części. Jeżeli twój wybór jest niepoprawny, wówczas powiem ci czy jest on zbyt wysoki lub zbyt niski, dzięki temu będziesz mógł wyeliminować około połowy niepoprawnych odpowiedzi. Na przykład, jeżeli obecny zakres możliwych odpowiedzi jest pomiędzy 26 a 80, możesz wybrać punkt środkowy $(26+80)/2$‍, czyli 53. Jeżeli powiem wtedy, że liczba 53 jest zbyt wysoka, wówczas możesz wyeliminować wszystkie liczby od 53 do 80, pozostawiając liczby od 26 do 52 jako nowy zakres możliwych odpowiedzi, pomniejszony o połowę.

Dla gry zgadywanie liczb, możemy śledzić zestaw możliwych odpowiedzi za pomocą kilku zmiennych. Przyjmijmy, że w tej rundzie zmienna $min$‍ będzie naszą najmniejszą, a zmienna $max$‍ największą możliwą odpowiedzią. Daną wejściową do problemu jest liczba $n$‍, największa możliwa liczba, jaką nasz przeciwnik ma na myśli. Zakładamy, że najniższą możliwą liczbą jest 1, ale można by było łatwo zmodyfikować algorytm uznając najniższą możliwą liczbę, jako drugą zmienną wejściową.

Tak działa, krok po kroku, algorytm wyszukiwania binarnego w przypadku gry w zgadywanie liczb:

Możemy sprawić, aby ten opis był jeszcze dokładniejszy, poprzez lepsze opisanie danych wejściowych oraz wyjściowych tego algorytmu, a także poprzez wyjaśnienie, co rozumiemy przez instrukcje "odgadłeś liczbę" i "stop". Ale na razie tyle szczegółów nam wystarczy.

Przejdziemy teraz do zagadnienia wykorzystania wyszukiwania binarnego w celu przeszukania macierzy i zastanowimy się, w jaki sposób przekształcić opis programu w działający kod.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormen i Devina Balkcom oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.