Binary search znajduje cel w posortowanej tablicy poprzez wielokrotne zmniejszanie zakresu wyszukiwania o połowę. Każde porównanie eliminuje połowę pozostałych elementów, co daje złożoność O(log n).
Spójrz na element środkowy. Jeśli jest równy celowi, gotowe. Jeśli cel jest mniejszy, przeszukaj lewą połowę; jeśli większy, przeszukaj prawą połowę. Powtarzaj, aż znajdziesz lub zakres będzie pusty.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1 # not present
binary_search([1, 3, 5, 7, 9], 7) # -> 3
Search 7 in [1,3,5,7,9]
lo=0 hi=4 mid=2 -> 5 < 7 => lo=3
lo=3 hi=4 mid=3 -> 7 == 7 => return 3
Wejście musi być posortowane — w przeciwnym razie wyniki są bez znaczenia. Uważaj na błędy off-by-one w lo/hi i przepełnienie liczb całkowitych w niektórych językach (użyj lo + (hi-lo)//2).
Połówkowanie przestrzeni wyszukiwania zamienia milionowe wyszukiwanie w ~20 porównań.
Wzorzec dziel i zwyciężaj za nim stojący pojawia się ponownie w drzewach, bazach danych i niezliczonych pytaniach z rozmów.
Znajomość jednego twardego wymagania — posortowanego wejścia — chroni cię przed klasycznym subtelnym błędem.