Czas działania wyszukiwania binarnego

Wiemy, że wyszukiwanie liniowe w tablicy o $n$n elementach może zająć $n$n sprawdzeń. Prawdopodobnie intuicja podpowiada ci, że wyszukiwanie binarne zajmuje mniej kroków niż wyszukiwanie liniowe. Może nawet dostrzegłeś, że różnica pomiędzy najgorszym przypadkiem wyszukiwania liniowego a wyszukiwania binarnego staje się bardziej znacząca wraz ze wzrostem długości tablicy. Zobaczmy jak możemy przeanalizować maksymalną liczbę prób, jaką wykonuje wyszukiwanie binarne.

Kluczową ideą wyszukiwania binarnego jest redukcja o połowę ilości danych do przeszukania podczas niepoprawnej próby. Jeżeli ilość elementów, z których możemy dokonać wyboru wynosi 32, wówczas przy niepoprawnej próbie odgadnięcia zmniejszamy ją do 16. Wyszukiwanie binarne zmniejsza o połowę ilość danych do przeszukania za każdą nieudaną próbą odgadnięcia.

Jeżeli rozpoczniemy z tablicą o długości wynoszącej 8, wówczas niepoprawna próba zredukuje jej rozmiar do 4, następnie do 2, a w ostatnim kroku do 1. Jeżeli ilość możliwych elementów wynosi tylko jeden, wówczas nie dochodzi do ponownej próby odgadnięcia; ten element jest wartością, której szukamy lub też nie i na tym kończymy przeszukiwanie. Więc przy długości tablicy wynoszącej 8, wyszukiwanie binarne potrzebuje, co najwyżej czterech prób.

Co sądzisz by się stało z tablicą złożoną z 16 elementów? Jeżeli uważasz, że pierwsza próba wyeliminuje przynajmniej 8 z nich, a pozostanie, co najwyżej 8 elementów, wówczas wiesz już, o co chodzi. Więc, aby przeszukać tablicę złożoną z 16 elementów potrzebujemy, co najwyżej pięciu prób.

Teraz prawdopodobnie widzisz już wzór. Za każdym razem, kiedy podwajamy wielkość tablicy, potrzebujemy, co najwyżej jednej próby więcej. Załóżmy, że potrzebujemy co najwyżej $m$m prób dla tablicy o długości $n$n. Następnie, dla tablicy o długości $2n$2, n, pierwsza próba zmniejsza nam liczbę możliwych odpowiedzi w tablicy do $n$n, z liczbą prób co najwyżej $m$m dlatego dla podwojonej tablicy uzyskujemy co najwyżej $m+1$m, plus, 1 prób.

Przyjrzyjmy się co się dzieje w ogólnym przypadku, gdy chcemy przeszukać macierz o długości $n$n. Liczbę prób w najgorszym przypadku możemy opisać jako "liczbę możliwych podziałów na pół macierzy o długości $n$n, aż do otrzymania macierzy o długości 1, dodać 1." Tyle, że ta formuła jest dość kłopotliwa do zapisywania za każdym razem.

Na szczęście istnieje funkcja matematyczna, która oznacza to samo, co liczbę razy, jaką musimy podzielić tablicę, począwszy od $n$n, dopóki nie otrzymamy wartości 1: jest to logarytm o podstawie 2 z $n$n. Najczęściej oznaczamy ją przez $\log_2 n$log, start base, 2, end base, n, choć czasem możesz napotkać zapis $\lg n$\lg, n. (Więcej o logarytmach dowiesz się tutaj.)

Poniżej znajduje się tabela przedstawiająca logarytm o podstawie 2 dla różnych wartości $n$n:

Możemy zobaczyć tę samą tabelę, jako wykres:

Powiększenie dla mniejszych wartości n:

Funkcja logarytmiczna rośnie bardzo powoli. Logarytmy są odwrotnością potęgowania, które rośnie bardzo szybko, więc jeśli $\log_2 n = x$log, start base, 2, end base, n, equals, x, wówczas $n = 2^x$n, equals, 2, start superscript, x, end superscript. Na przykład, ponieważ $\log_2 128 = 7$log, start base, 2, end base, 128, equals, 7, mamy $2^7 = 128$2, start superscript, 7, end superscript, equals, 128.

W ten sposób możemy łatwo obliczyć czas wykonania algorytmu przeszukiwania binarnego dla $n$n będącego potęgą 2. Dla $n$n równego 128, przeszukiwanie binarne będzie potrzebować co najwyżej 8 ($\log_2 128 + 1$log, start base, 2, end base, 128, plus, 1) kroków.

Co zrobić, jeśli $n$n nie jest potęgą 2? W takim przypadku powinniśmy znaleźć największą liczbę, którą można przedstawić jako potęgę 2 i która jest mniejsza od $n$n. Na przykład, w przypadku macierzy, która ma 1000 elementów, największa potęga 2, która jest zarazem mniejsza od 1000, wynosi 512, czyli $2^{9}$2, start superscript, 9, end superscript. Możemy więc oszacować, że $\log_2 1000$log, start base, 2, end base, 1000 jest liczbą większą od 9, a mniejszą od 10, albo wyciągnąć od razu kalkulator i obliczyć, że logarytm równa się około 9,97. Dodając jeden otrzymamy 10,97, po czym zaokrąglamy do najbliższej mniejszej liczby całkowitej. A zatem, w przypadku macierzy o 1000 elementach, przeszukiwanie binarne wymagać będzie co najwyżej 10 prób.

W katalogu gwiazd Tycho-2 znajduje się 2 539 913 gwiazd. Największa liczba będącą potęgą 2 i jednocześnie mniejsza od liczby gwiazd w katalogu wynosi $2^{21}$2, start superscript, 21, end superscript (czyli 2 097 152), a zatem będziemy potrzebować co najwyżej 22 prób. Dużo lepiej, niż w przypadku przeszukiwania liniowego!

Na poniższym wykresie porównano $n$n z $\log _{2} n$log, start base, 2, end base, n:

W następnym ćwiczeniu zobaczymy jak informatycy określają czas pracy wyszukiwania liniowego oraz wyszukiwania binarnego, przy użyciu notacji, która bierze pod uwagę jedynie najważniejszą część związaną z czasem pracy algorytmu, a pomija te mniej istotne.

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