Wyszukiwanie binarne

Formalne przedstawienie problemu

Dane wejściowe:

Ciąg n posortowanych rosnąco liczb A= 〈a_1,a_2,…,a_n 〉 i wartość v.

Wynik:

Indeks i taki, że v=A[i], lub wartość specjalna NIL, jeśli v nie występuje w A.

Rozwiązanie

W wyszukiwaniu binarnym korzystamy z założenia, że ciąg jest posortowany. Należy sprawdzać środkowy element danego przedziału – dzięki temu przy każdym porównaniu można odrzucić połowę tablicy.

Złożoność

Czasowa: O(log2⁡n )

Sposób postępowania

Użyta metoda - Dziel i zwyciężaj

Wyjaśnienie działania algorytmu

Jest dana tablica posortowanych liczb. Nasze zadanie polega na znalezieniu wśród nich elementu v lub poinformowanie, że taki element nie znajduje się w tablicy. Naiwnym podejściem byłoby przeszukanie całego ciągu od pierwszego do ostatniego elementu – dałoby to algorytm o złożoności liniowej. Można to zrobić lepiej – używając wyszukiwania binarnego. Korzystamy tu z założenia, że tablica jest posortowana rosnąco.

Przez low i high oznaczmy odpowiednio indeks początkowy i końcowy przeszukiwanego w danym momencie przedziału. Inicjalizujemy je, w C++, wartościami 0 i n. W tym momencie rozpoczyna się pętla while, która działa, dopóki low<high. Sprawdzamy środkowy element, czyli ten o indeksie mid= ⌊(low+high)/2⌋ (⌊x⌋ to największa liczba całkowita nie większa od x, czyli „zaokrąglenie w dół”). Możliwe są trzy przypadki:

    • v=A[mid] wówczas program znalazł poszukiwany element – kończymy program i zwracamy indeks mid

    • v<A[mid], poszukiwany element znajduje się w części od low do mid – za dotychczasowe high należy podstawić mid

    • v>A[mid], czyli poszukiwany element znajduje się w części od mid+1 do high - za dotychczasowe low należy podstawić mid+1

Następuje kolejny obieg pętli while i wartości low, mid i high są odpowiednio aktualizowane. Pętla while kończy się, kiedy zostaje zwrócony indeks poszukiwanego elementu albo kiedy low ≥high - to oznacza, że nie znaleziono poszukiwanego elementu.

Takie rozwiązanie pozwala przeszukać zbiór liczący 1 000 000 elementów w 20 sprawdzeniach!

Implementacja