Realizacja 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:

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:

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:

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:

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.