Wyszukiwanie binarne

Specyfikacja problemu:

Dane:

• n – liczba naturalna; liczba elementów tablicy tablica

• tablica – n-elementowa, uporządkowana rosnąco tablica liczb naturalnych

• szukana – liczba naturalna

Wynik:

• komunikat wskazujący indeks, pod którym znajduje się szukana liczba, lub informujący, że w tablicy nie ma szukanej liczby

Algorytm wyszukiwania binarnego wyszukuje wybrany element w posortowanym w zbiorze. 

Zasada działania algorytmu nie zmienia się. Algorytm nie wywołuje się rekurencyjnie, wykorzystujemy natomiast pętlę dopóki.

Zapisujemy nagłówek funkcji wyszukiwanie_binarne_iter. Przyjmie ona cztery argumenty – tablicę liczb, szukaną wartość, indeks początku oraz indeks końca.

W kolejnym kroku określimy środek analizowanego przedziału, przypisując zmiennej środek wartość dzielenia całkowitego sumy wartości zmiennych pocz oraz kon przez liczbę 2.

Następnie zapiszemy instrukcję warunkową jeżeli. Sprawdzamy, czy szukana liczba jest równa wartości elementu tablicy o indeksie równym wartości zmiennej środek. Jeśli tak, wypisujemy odpowiedni komunikat.

Jeśli element nie jest równy elementowi przechowywanemu pod indeksem środek, sprawdzamy, czy jest on od niego mniejszy. Jeśli tak, zmieniamy wartość zmiennej pocz, przypisując jej wartość sumy zmiennej środek oraz liczby 1.

Jeżeli element jest mniejszy, przypisujemy zmiennej kon wartość różnicy zmiennej środek oraz liczby 1.

Jeśli po wyjściu z pętli dopóki element nie został znaleziony, wypisujemy odpowiedni komunikat.

funkcja wyszukiwanie_binarne_iter(tablica, szukana, pocz, kon):
	dopóki pocz <= kon:
    	środek ← (pocz + kon) div 2     
    	jeżeli tablica[środek] = szukana:
    		wypisz "Znaleziono liczbę na pozycji " + środek
            zwróć środek
    	w przeciwnym wypadku jeżeli tablica[środek] < szukana:
    		pocz = środek + 1
    	w przeciwnym wypadku:
    		kon = środek - 1
            
	wypisz "Nie znaleziono szukanej liczby"

Algorytm wyszukiwania binarnego działa przez podział zakresu wyszukiwania na dwie równe części i wybór tej, która zawiera szukaną wartość (lub może ją zawierać). Dzięki temu zakres wyszukiwania jest dzielony na pół w każdej iteracji. W konsekwencji każdy podział sprowadzi problem do problemu o połowę mniejszego.

W związku z tym, jeżeli mamy tablicę o długości $n$, to w najgorszym wypadku potrzebujemy $O\left(\log n\right)$ podziałów, aby zawęzić zakres wyszukiwania do jednego elementu. Stąd złożoność czasowa wynosi $O\left(\log n\right)$.

Słownik