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);

Q: 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);

Ponadto w funkcji powinno się podać array[guess] zamiast primes[guess]. Dopiero przy wywoływaniu funkcji parametr array pobiera wartość zmiennej primes: var result = doSearch(primes, 73);

Główna zawartość

Kurs: Informatyka > Rozdział 1

Lekcja 2: Wyszukiwanie binarne

Czas działania wyszukiwania binarnego

Google Classroom

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

2 n

, 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

\log_{2} n

, choć czasem możesz napotkać zapis

\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$ ‍	$\log_{2} n$ ‍
1	0
2	1
4	2
8	3
16	4
32	5
64	6
128	7
256	8
512	9
1024	10
1 048 576	20
2 097 152	21

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

, wówczas

n = 2^{x}

. Na przykład, ponieważ

\log_{2} 128 = 7

, mamy

2^{7} = 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 (

\log_{2} 128 + 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

2^{9}

. Możemy więc oszacować, że

\log_{2} 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}

(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

\log_{2} 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?

Zaloguj się

Sortuj według

agar
Opublikowane 7 lat temu. Odnosi się do postu agar's o treści “Co jest tu źle: var pri...”
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);
Kliknij, aby przejść do strony rejestracjiSkomentuj wpis użytkownika agar o treści „Co jest tu źle: var pri...”
(1 głos)
Odpowiedź
- Justyna Wacławowicz
  Opublikowane 6 lat temu. Odnosi się do postu Justyna Wacławowicz's o treści “Ponadto w funkcji powinno...”
  Ponadto w funkcji powinno się podać array[guess] zamiast primes[guess].
  Dopiero przy wywoływaniu funkcji parametr array pobiera wartość zmiennej primes:
  var result = doSearch(primes, 73);
  Kliknij, aby przejść do strony rejestracji
  (3 głosy)

Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.