Algorytm wyszukiwania binarnego, wykorzystujący technikę "dziel i zwyciężaj", jest skutecznym algorytmem służący do znajdowania określonego elementu w posortowanym zbiorze danych. Polega on na podziale tego zbioru na pół i porównywaniu poszukiwanego elementu z elementem w środku zbioru. Na podstawie wyniku tego porównania algorytm decyduje, czy poszukiwany element znajduje się w lewej czy prawej części zbioru i powtarza ten proces na odpowiedniej połowie zbioru. Wyszukiwanie binarne jest wydajne, ponieważ po każdej iteracji eliminuje połowę zbioru jako potencjalne miejsce, w którym znajduje się poszukiwany element.
Przeanalizujmy przykład:$$1\ 2\ 4\ 7\ 8\ 9\ 11$$wyszukując liczbę 8.
Wyszukiwanie binarne jest znacznie bardziej efektywne niż liniowe przeszukiwanie, które wymagałoby sprawdzenia każdego elementu w zbiorze. Jego złożoność obliczeniowa wynosi $$O(log n)$$, gdzie "n" to liczba elementów w zbiorze. Jest to więc szybki sposób na odnalezienie elementu w dużych, posortowanych zbiorach danych.
Dla zadanego zbioru n uporządkowanych niemalejąco liczb całkowitych określ, na której pozycji znajduje się liczba szukana s. Jeśli liczba nie występuje w zbiorze, to zwróć -1. Elementy zbioru numerujemy od 0 do n - 1.
Rozwiązanie iteracyjne:
#****************algorytm.edu.pl**************
def binary_search(zbior, s): # zbiór - uporządkowany zbiór liczb, s - wartość szukana
l = 0 # indeks pierwszego elementu w zbiorze
p = len(zbior) - 1 # indeks ostatniego elementu w zbiorze
while l <= p:
sr = (l + p)//2 # wyznaczamy indeks środkowego elementu zbioru
if s == zbior[sr]: # jeśli znaleźliśmy szukaną wartość
return sr
if s < zbior[sr]: # jeśli szukana wartość jest mniejsza od elementu środkowego
p = sr - 1 # to ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [l, sr - 1]
else: # w przeciwnym razie
l = sr + 1 # ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [sr + 1, p]
return -1 # jeśli nie znaleziono szukanej wartości
#************główna część programu*****************
zbior = [1, 2, 5, 7, 9, 12, 14, 19] # uporządkowany zbiór liczb
s = 9
if binary_search(zbior, s) == -1:
print("nie znaleziono liczby", s)
else:
print("Liczba", s, "znajduje się pod indeksem", binary_search(zbior, s))
Liczba 9 znajduje się pod indeksem 4
Rozwiązanie rekurencyjne:
#****************algorytm.edu.pl**************
def binary_search(zbior, s, l, p): # zbiór - uporządkowany zbiór liczb, s - wartość szukana,
# l - lewy indeks podtablicy, p - prawy indeks podtablicy
if l >p: return -1 # jeśli nie znaleziono szukanej wartości
sr = (l + p)//2 # wyznaczamy indeks środkowego elementu zbioru
if s == zbior[sr]: # jeśli znaleźliśmy szukaną wartość
return sr
if s < zbior[sr]: # jeśli szukana wartość jest mniejsza od elementu środkowego
return binary_search(zbior, s, l, sr - 1) # to ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [l, sr - 1]
else: # w przeciwnym razie
return binary_search(zbior, s, sr + 1, p) # to ograniczamy przeszukiwanie do zbioru dla indeksów z przedziału [sr + 1, p]
#************główna część programu*****************
zbior = [1, 2, 5, 7, 9, 12, 14, 19] # uporządkowany zbiór liczb
s = 9
if binary_search(zbior, s, 0, len(zbior) - 1) == -1:
print("nie znaleziono liczby", s)
else:
print("Liczba", s, "znajduje się pod indeksem", binary_search(zbior, s, 0, len(zbior) - 1))