Binary search vindt een doel in een gesorteerde array door het zoekbereik herhaaldelijk te halveren. Elke vergelijking elimineert de helft van de resterende elementen, wat O(log n) tijd oplevert.
Kijk naar het middelste element. Als het gelijk is aan het doel, klaar. Als het doel kleiner is, zoek je in de linkerhelft; als het groter is, zoek je in de rechterhelft. Herhaal tot je het hebt gevonden of het bereik leeg is.
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
De invoer moet gesorteerd zijn — anders zijn de resultaten betekenisloos. Let op off-by-one bugs in lo/hi en integer overflow in sommige talen (gebruik lo + (hi-lo)//2).
Het halveren van de zoekruimte verandert een miljoen-element zoekopdracht in ~20 vergelijkingen.
Het divide-and-conquer patroon erachter komt terug in bomen, databases en talloze interview problemen.
Weten dat het één harde vereiste heeft — gesorteerde invoer — houdt je weg van een klassieke subtiele bug.