Wyszukiwanie binarne (wersja rekurencyjna)

W przypadku wyszukiwania binarnego wybierany jest element środkowy, względem którego ciąg jest dzielony na dwie części. Sprawdzamy, czy środkowy element jest poszukiwanym elementem. Jeśli nie, sprawdzamy, czy środkowy element jest większy, czy mniejszy od poszukiwanego elementu. Zależnie od tego wybieramy tylko lewy albo prawy podciąg, czyli działamy wyłącznie na jednej z wydzielonych części.

Zaprezentujmy działanie algorytmu na konkretnym przykładzie.

Dany jest następujący posortowany ciąg liczb całkowitych:

[1,2,5,9,12,15,27,50,94,100]

• Lewą najmniejszą liczbą w tym ciągu jest liczba 1 (indeks 0).

• Prawą najmniejszą liczbą w tym ciągu jest liczba 100 (indeks 9).

• Poszukujemy pozycji liczby 27.

Chcemy wyznaczyć indeks elementu środkowego. Dodajemy do siebie indeksy lewej i prawej najmniejszej liczby w tym ciągu – otrzymujemy liczbę 9. Dzielimy ją całkowicie przez 2. Otrzymujemy wynik 4.

Pod indeksem 4 znajduje się liczba 12. Szukana liczba jest od niej większa, zatem wiemy, że liczby o indeksach 4 i mniejszych nie będą już brane pod uwagę.

Zostaje podciąg składający się z liczb większych od 12:

[15,27,50,94,100]

Lewą najmniejszą liczbą w tym ciągu zostaje liczba o indeksie 5, czyli liczba 15.

Prawą najmniejszą liczbą w tym ciągu zostaje liczba 100 o indeksie 9.

Ponownie dodajemy do siebie wartości indeksów i dzielimy je całkowicie przez 2. Otrzymany wynik to 7.

Liczbą o indeksie równym 7 jest 50.

Poszukiwana liczba 27 jest od niej mniejsza, więc szukany element może się znajdować na miejscach o indeksach od 5 do 7.

Teraz analizowany podciąg wygląda następująco:

[15,27,50]

Ponawiamy dodawanie do siebie indeksów. Tym razem środkiem zostaje liczba o indeksie 6. Jest to liczba 27, czyli poszukiwana wartość.

Zapiszmy analizowany algorytm za pomocą pseudokodu:

funkcja wyszukiwanie_binarne(tablica, szukana, pocz, kon):
	jeżeli pocz > kon:
    	zwróć -1
    
    środek ← (pocz + kon) div 2
    jeżeli tablica[środek] = szukana:
    	zwróć środek
    w przeciwnym wypadku jeżeli tablica[środek] < szukana:
    	zwróć wyszukiwanie_binarne(tablica, szukana, środek + 1, kon)
    w przeciwnym wypadku:
    	zwróć wyszukiwanie binarne(tablica, szukana, pocz, środek - 1)

Tak wygląda rozwiązanie rekurencyjne.