Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 1
Lekcja 2: Wyszukiwanie binarneRealizacja przeszukiwania binarnego macierzy.
Zastanówmy się nad wyszukiwaniem binarnym w posortowanej tablicy. JavaScript (oraz wiele innych języków) dostarcza metody służące określeniu czy dany element jest w tablicy i, jeżeli jest, na którym miejscu się znajduje. Jednak my chcemy zaimplementować tę funkcjonalność samemu, aby zrozumieć w jaki sposób działa. Poniżej znajduje się uporządkowana tablica 25 początkowych liczb pierwszych napisana w JavaScripcie:
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];
Załóżmy, że chcemy się dowiedzieć, czy 67 jest liczbą pierwszą. W tym celu wystarczy sprawdzić, czy znajduje się w powyższej tablicy.
Możemy również chcieć poznać ilość liczb pierwszych mniejszych niż 67. Jeśli znajdziemy pozycję liczby 67, będziemy wiedzieli ile elementów naszej tablicy (a więc liczb pierwszych) znajduje się przed nią.
Położenie elementu w tablicy nazywane jest jego indeksem. Numeracja indeksów tablic zaczyna się od 0 i postępuje rosnąco. Jeśli dany element ma indeks równy 0, jest on pierwszym elementem tablicy. Jeśli dany element ma indeks równy 3, posiada 3 poprzedzające go elementy.
W poniższej przykładowej tablicy możemy odczytywać kolejne liczby od lewej do prawej aż nie znajdziemy liczby 67 i dowiemy się, że jej indeks wynosi 18. Takie przeglądanie wszystkich liczb po kolei zwane jest przeszukiwaniem liniowym.
Kiedy już wiemy, że liczba 67 posiada indeks równy 18 możemy stwierdzić, że jest liczbą pierwszą. Możemy również w prosty sposób stwierdzić, że przed liczbą 67 jest 18 elementów, więc istnieje 18 liczb pierwszych mniejszych niż 67.
Czy widzisz ile to zajęło kroków? Wyszukiwanie binarne może być bardziej wydajne. Ponieważ tablica
primes
zawiera 25 liczb, ich indeksy mieszczą się w zakresie od 0 do 24. Używając naszego pseudokodu zaczynamy poprzez ustawienie wartości min
= 0 oraz max
= 24. Pierwsza wartość rozpatrywana w wyszukiwaniu binarnym będzie więc miała indeks 12 (czyli (0 + 24) / 2). Czy primes[12]
równa się 67? Nie, primes[12]
równa się 41.Czy szukany przez nas indeks jest wyższy czy niższy niż 12? Ponieważ liczby w tablicy są posortowane rosnąco, a 41 < 67, wartość 67 powinna być na prawo od indeksu 12. Inaczej ujmując, kolejny rozpatrywany przez nas indeks powinien być większy od 12. Aktualizujemy wartość
min
na 12 + 1, czyli 13, natomiast max
zostawiamy na 24 bez zmian.Jaki indeks powinien być teraz przez nas rozpatrywany? Średnia arytmetyczna liczb 13 i 24 wynosi 18.5, co możemy zaokrąglić do 18, ponieważ indeks musi być liczbą całkowitą. W ten sposób dowiadujemy się, że
primes[18]
wynosi 67.Algorytm wyszukiwania binarnego zatrzymuje się na tym etapie, gdyż znalazł odpowiedź. Zamiast 19 rozpatrywanych elementów w przypadku wyszukiwania liniowego teraz starczyły nam tylko 2. Możesz obejrzeć ten proces na poniższej wizualizacji:
Pseudokod
Właśnie opisaliśmy słownie sposób działania algorytmu wyszukiwania binarnego posługując się przykładową tablicą. Niestety język naturalny nie zawsze jest odpowiedni. Wyjaśnienie może być zbyt krótkie, zbyt długie lub, co najważniejsze, niewystarczająco precyzyjne. Moglibyśmy od razu zacząć pokazywać implementację wyszukiwania binarnego w językach programowania takich jak JavaScript lub Python, ale programy zawierają mnóstwo szczegółów - z uwagi na wymagania nałożone przez język programowania lub ponieważ programy muszą sobie radzić z wszelkiego rodzaju błędami, zarówno spowodowanymi przez system jak i przez użytkownika. Te dodatkowe elementy kodu mogą znacznie utrudnić zrozumienie istoty danego algorytmu. Dlatego właśnie wolimy opisywać algorytmy w tzw. pseudokodzie, czyli przejrzystym połączeniu języka naturalnego z popularnymi elementami języków programowania.
Poniżej znajduje się zapisany w pseudokodzie algorytm wyszukiwania binarnego, zmodyfikowany na potrzeby wyszukiwania w tablicy. Na wstępie program dostaje tablicę, którą nazwiemy
array
, liczba n
elementów w array
, oraz target
, szukaną przez nas liczbę. Na wyjściu dostajemy indeks w array
elementu target
:- Niech
min = 1
imax = n - 1
. - Wyznacz
guess
jako średniąmax
imin
, zaokrągloną w dół (do najbliższej liczby całkowitej). - Jeśli
array[guess]
jest równetarget
, wtedy zakończ. Liczba jest znaleziona! Zwróćguess
. - Jeśli strzeliliśmy za nisko, czyli
array[guess] < target
, ustawmin = guess + 1
. - W przeciwnym przypadku strzeliliśmy za wysoko. Ustaw
max = guess - 1
. - Powróć do kroku 2.
Implementacja pseudokodu
Będziemy wykorzystywali zarówno język naturalny, pseudokod jak i JavaScript w tych samouczkach, w zależności od sytuacji. Jako programista powinieneś nauczyć się rozumieć pseudokod i móc przekształcić go w wybrany przez siebie język. Pomimo tego, że tutaj korzystamy z JavaScriptu, implementacja pseudokodu w innych językach nie powinna sprawić Ci problemów.
Jak więc zamienić ten pseudokod w program w JavaScripcie? Powinniśmy stworzyć funkcję, ponieważ piszemy kod, który pobiera informacje na wejściu i zwraca informacje na wyjściu, oraz chcemy aby kod był poprawny dla różnych informacji wejściowych. Parametrami naszej funkcji (nazwijmy ją
binarySearch
) będą tablica oraz szukany element, natomiast zwracać będzie indeks elementu, którego szukamy.Przejdźmy więc do ciała funkcji i zastanówmy się jak je zaimplementować. Krok 6. nakazuje powrót do kroku 2. To wygląda na pętlę. Czy to powinna być pętla for czy while? Oczywiście, jeśli bardzo chcesz to możesz użyć pętli for, natomiast brak sekwencyjnego charakteru rozpatrywanych indeksów pozbawia ją największych zalet. Najpierw możemy rozpatrywać indeks 12 a następnie 18 bazując na naszych obliczeniach, Tak więc pętla while jest w tym przypadku lepszym rozwiązaniem.
Brakuje nam również jednego bardzo ważnego kroku w pseudokodzie, który do tej pory nie miał dla nas znaczenia, natomiast ma w przypadku wyszukiwania elementów w tablicy. Co by się stało, gdyby szukanego przez nas elementu nie było w tablicy? Zacznijmy poprzez ustalenie indeksu zwracanego przez funkcję
binarySearch
w takim wypadku. Musi to być liczba, która nie może być uznana za prawidłowy indeks tablicy. Użyjemy -1
gdyż, jak wcześniej ustaliliśmy, indeksy tablicy numeruje się od liczby 0 wzwyż. (Tak naprawdę dowolna liczba ujemna byłaby poprawna.)Poszukiwanej liczby nie ma w tablicy, jeśli nie można wyznaczyć zakresu do rozpatrzenia przy jej wyszukiwaniu. W naszym przykładzie załóżmy, że poszukujemy liczby 10 w tablicy
primes
. Gdyby tam była, to pomiędzy liczbami 7 i 11, które są pod indeksami 3 i 4. Jeśli prześledzić zmiany indeksów min
i max
podczas wykonywania funkcji binarySearch
, to się okaże, że osiągną one wartości 3 dla min
i 4 dla max
. Zatem algorytm rozpatrzy indeks 3 jako kolejny punk podziału zakresu - (3+4)/2 daje 3,5, co po zaokrągleniu w dół da 3 - a że primes[3]
jest mniejsze od 10, w kolejnym korku min
zostanie przypisana wartość 4. Mając obie wartości - min
i max
- równe 4, poszukiwana liczba musi być pod indeksem 4, a primes[4]
jest większe od 10. W takim przypadku max
otrzymuje wartość 3. Jak zatem rozumieć sytuację, kiedy min
wynosi 4, a max
3? Zatem, kiedy poszukiwana wartość jest pod indeksem co najmniej 4 i co najwyżej 3? Nie ma takiej liczby! W tym momencie możemy wywnioskować, że poszukiwanej liczby 10 nie ma w tablicy primes
, a funkcja binarySearch
powinna zwrócić -1
. W ogólnym przypadku, kiedy max
staje się ściśle mniejsze od min
wiemy, że poszukiwanej liczby nie ma w posortowanej tablicy. Poniżej jest zmodyfikowany pseudokod obsługujący przypadek braku poszukiwanej liczby:- Niech
min = 1
imax = n - 1
. - Jeśli
max < min
, zakończ:target
nie jest elementem tablicyarray
. Zwróć-1
. - Wyznacz
guess
jako średniąmax
imin
, zaokrągloną w dół (do najbliższej liczby całkowitej). - Jeśli
array[guess]
jest równetarget
, wtedy zakończ. Liczba jest znaleziona! Zwróćguess
. - Jeśli strzeliliśmy za nisko, czyli
array[guess] < target
, ustawmin = guess + 1
. - W przeciwnym przypadku strzeliliśmy za wysoko. Ustaw
max = guess - 1
. - Powróć do kroku 2.
Teraz, gdy już wspólnie omówiliśmy pseudokod, spróbuj samemu zaimplementować algorytm wyszukiwania binarnego. Nie bój się patrzeć na pseudokod. Tak naprawdę do tego zachęcam, ponieważ ugruntuje to Twoją wiedzę na temat przekształcania pseudokodu w program.
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?
- Dlaczego w pseudokodzie w punkcie 1. max = n - 1?
Zamiast max = n
Byłoby to logiczne w przypadku gdyby min było równe 0 (zgodnie z indexowaniem elementów tablicy w większości języków programowania) ale w przykładzie min = 1(6 głosów)- Mimo to, ze deklarujesz "min" jako element o indexie 1, nie usuwasz z tablicy elementu o indexie 0. Aby otrzymac index ostatniego elementu, musisz odjac jeden od dlugosci calej tablicy. Dla przykladu kod javascript:
var tablica =[a,b,c,d,e,f,g,h,i];
var dlugosc = tablica.length - 1;// 9 - 1
var min = tablica[1]
var max = tablica[dlugosc];
console.log(min, max)
//konsola wypluje nam "b, i"(6 głosów)
- b r u h wy tutaj na angielski narzekacie(1 głos)
- gdzie jest moj tata? ;((0 głosów)