Binary search găsește o țintă într-un array sortat prin înjumătățirea repetată a intervalului de căutare. Fiecare comparație elimină jumătate din elementele rămase, oferind timp O(log n).
Priviți elementul din mijloc. Dacă este egal cu ținta, gata. Dacă ținta este mai mică, căutați în jumătatea stângă; dacă este mai mare, căutați în jumătatea dreaptă. Repetați până când găsiți sau intervalul este gol.
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
Intrarea trebuie să fie sortată — în caz contrar, rezultatele sunt lipsite de sens. Atenție la erori off-by-one în lo/hi și depășire de intregi în unele limbaje (utilizați lo + (hi-lo)//2).
Înjumătățirea spațiului de căutare transformă o căutare cu un milion de elemente în ~20 comparații.
Modelul divide-and-conquer din spatele său reapare în arbori, baze de date și nenumărate probleme de interviu.
Cunoașterea singurul său requisit strict — intrare sortată — te ține departe de o eroare subtilă clasică.