Binärsuche findet ein Ziel in einem sortierten Array, indem sie den Suchbereich wiederholt halbiert. Jeder Vergleich eliminiert die Hälfte der verbleibenden Elemente und ergibt eine O(log n)-Zeit.
Schauen Sie sich das mittlere Element an. Wenn es dem Ziel entspricht, sind Sie fertig. Wenn das Ziel kleiner ist, durchsuchen Sie die linke Hälfte; wenn es größer ist, durchsuchen Sie die rechte Hälfte. Wiederholen Sie, bis das Element gefunden wurde oder der Bereich leer ist.
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
Die Eingabe muss sortiert sein – andernfalls sind die Ergebnisse bedeutungslos. Achten Sie auf Off-by-one-Fehler in lo/hi und Integer-Überläufe in einigen Sprachen (verwenden Sie lo + (hi-lo)//2).
Das Halbieren des Suchraums verwandelt eine Suche mit einer Million Elementen in etwa 20 Vergleiche.
Das divide-and-conquer-Muster dahinter taucht in Bäumen, Datenbanken und unzähligen Interview-Problemen wieder auf.
Die Kenntnis seiner einen harten Anforderung – sortierte Eingabe – bewahrt Sie vor einem klassischen subtilen Fehler.