Wyszukiwanie Binarne

Małgorzata Piekarska

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(log_2⁡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

int bin_search(int v, int n)
{
    int low = 0;
    int high = n;
    int mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (v == A[mid]) return mid;
        else if (v < A[mid]) 
            high = mid;
        else // v> A[mid]
            low = mid + 1;
    }
    return -1 //nie znaleziono
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License