If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Czas działania wyszukiwania binarnego

Wiemy, że wyszukiwanie liniowe w tablicy o n elementach może zająć 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 prób dla tablicy o długości n. Następnie, dla tablicy o długości 2n, pierwsza próba zmniejsza nam liczbę możliwych odpowiedzi w tablicy do n, z liczbą prób co najwyżej m dlatego dla podwojonej tablicy uzyskujemy co najwyżej m+1 prób.
Przyjrzyjmy się co się dzieje w ogólnym przypadku, gdy chcemy przeszukać macierz o długości n. Liczbę prób w najgorszym przypadku możemy opisać jako "liczbę możliwych podziałów na pół macierzy o długości 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, dopóki nie otrzymamy wartości 1: jest to logarytm o podstawie 2 z n. Najczęściej oznaczamy ją przez log2n, choć czasem możesz napotkać zapis lgn. (Więcej o logarytmach dowiesz się tutaj.)
Poniżej znajduje się tabela przedstawiająca logarytm o podstawie 2 dla różnych wartości n:
nlog2n
10
21
42
83
164
325
646
1287
2568
5129
102410
1 048 57620
2 097 15221
Możemy zobaczyć tę samą tabelę, jako wykres:
Wykres funkcji logarytm o podstawie 2 z n dla dużych wartości n
Powiększenie dla mniejszych wartości n:
Wykres funkcji logarytm o podstawie 2 z n dla małych 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 log2n=x, wówczas n=2x. Na przykład, ponieważ log2128=7, mamy 27=128.
W ten sposób możemy łatwo obliczyć czas wykonania algorytmu przeszukiwania binarnego dla n będącego potęgą 2. Dla n równego 128, przeszukiwanie binarne będzie potrzebować co najwyżej 8 (log2128+1) kroków.
Co zrobić, jeśli 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. 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 29. Możemy więc oszacować, że log21000 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 221 (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 z log2n:
Porównanie n i logarytmu o podstawie 2 z 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.

Chcesz dołączyć do dyskusji?

  • Awatar blobby green style dla użytkownika agar
    Co jest tu źle:

    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

    var doSearch = function(array, targetValue) {
    var min = 0;
    var max = array.length - 1;
    var guess;

    guess = Math.floor((min+max)/2);
    while(min<=max){
    if(primes[guess]===targetValue){ return guess; }
    else if(primes[guess]<targetValue){ min=guess+1;}
    else{ max=guess-1; }
    }
    return -1;
    };



    var result = doSearch(primes, 73);
    println("Found prime at index " + result);

    Program.assertEqual(doSearch(primes, 73), 20);
    (1 głos)
    Awatar Default Khan Academy avatar dla użytkownika
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.