Wyszukiwanie binarne

Wyszukiwanie binarne

Wyszukiwanie binarne to algorytm wykorzystujący metodę dziel i zwyciężaj, który pozwala w czasie logarytmicznym określić, czy dany element znajduje się w uporządkowanej tablicy. W przypadku tablicy liczącej milion elementów, algorytm ten sprawdza maksymalnie 20 elementów (log₂(1,000,000) ≈ 20). Dla porównania, wyszukiwanie liniowe w najgorszym przypadku wymaga przeszukania wszystkich elementów.

Zasada działania algorytmu

Algorytm działa poprzez dzielenie uporządkowanej tablicy na coraz mniejsze przedziały, aż osiągnie przedział jednoelementowy, co pozwala na szybkie sprawdzenie obecności poszukiwanego elementu.

W każdym kroku algorytm analizuje przedział charakteryzowany dwoma indeksami: początkowym $a$ i końcowym $b$. Rozpoczyna od całej tablicy, a następnie oblicza środek przedziału $c\; =\; lfloor(a\; +\; b)\; /\; 2rfloor$. W zależności od wartości poszukiwanego elementu algorytm zawęża przedział do $[a,\; c]$ lub $[c+1,\; b]$.

Algorytm kończy się, gdy przedział staje się jednoelementowy, a wartość pod indeksem $a$ nie odpowiada poszukiwanej wartości.

Implementacja

Poniżej znajduje się przykładowa implementacja wyszukiwania binarnego w języku TypeScript:

/**
* Zwraca indeks poszukiwanego elementu
* lub null, jeśli element nie istnieje.
*
* @param tablica – posortowana tablica liczb.
* @param szukana – poszukiwana wartość.
*/
function wyszukiwanieBinarnie(tablica: number[], szukana: number): number | null {
let lewo = 0;
let prawo = tablica.length – 1;
while (lewo <= prawo) { let przeszukiwany_indeks = Math.floor((lewo + prawo) / 2); if (tablica[przeszukiwany_indeks] < szukana) { lewo = przeszukiwany_indeks + 1; } else if (tablica[przeszukiwany_indeks] > szukana) {
prawo = przeszukiwany_indeks – 1;
} else {
return przeszukiwany_indeks;
}
}
return null;
}

Wyszukiwanie interpolacyjne

Wariantem wyszukiwania binarnego jest wyszukiwanie interpolacyjne, które określa punkt podziału (indeks $c$) na podstawie wartości kluczy na krańcach przedziału. Złożoność obliczeniowa tego algorytmu wynosi średnio $Theta(log\; log\; n)$, co jest korzystniejsze niż w przypadku standardowego wyszukiwania binarnego ($O(log\; n)$), aczkolwiek w przypadku niejednorodnych danych osiąga złożoność liniową.

Metoda ta została opracowana w 1957 roku przez W.W. Petersona i znalazła zastosowanie w wyszukiwaniu elementów w posortowanych plikach.