Wyszukiwanie binarne to algorytm służący do znajdowania elementu w posortowanym zbiorze danych, np. w tablicy liczb uporządkowanej rosnąco.
Algorytm porównuje szukaną wartość z elementem środkowym. Jeśli wartość jest równa elementowi środkowemu, wyszukiwanie kończy się sukcesem. Jeśli jest mniejsza, dalsze szukanie odbywa się w lewej połowie tablicy. Jeśli jest większa, w prawej połowie.
Warunek działania
Najważniejszy warunek: dane muszą być wcześniej posortowane. Bez tego algorytm może zwrócić błędny wynik.
Wersja iteracyjna
Wersja iteracyjna wykorzystuje pętlę, np. while.
def binary_search(tab, x):
left = 0
right = len(tab) - 1
while left <= right:
mid = (left + right) // 2
if tab[mid] == x:
return mid
elif x < tab[mid]:
right = mid - 1
else:
left = mid + 1
return -1
Wersja rekurencyjna
Wersja rekurencyjna wywołuje samą siebie dla coraz mniejszego fragmentu tablicy.
def binary_search_rec(tab, x, left, right):
if left > right:
return -1
mid = (left + right) // 2
if tab[mid] == x:
return mid
elif x < tab[mid]:
return binary_search_rec(tab, x, left, mid - 1)
else:
return binary_search_rec(tab, x, mid + 1, right)
Złożoność
Wyszukiwanie binarne ma złożoność czasową O(log n), ponieważ w każdym kroku odrzuca połowę danych. Jest znacznie szybsze od wyszukiwania liniowego dla dużych, posortowanych zbiorów.