La ricerca binaria trova un elemento bersaglio in un array ordinato dimezzando ripetutamente l'intervallo di ricerca. Ogni confronto elimina metà degli elementi rimanenti, fornendo una complessità di O(log n).
Guarda l'elemento centrale. Se corrisponde al bersaglio, hai finito. Se il bersaglio è più piccolo, cerca nella metà sinistra; se è più grande, cerca nella metà destra. Ripeti fino a trovarlo o finché l'intervallo non è vuoto.
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
L'input deve essere ordinato — altrimenti i risultati sono privi di significato. Stai attento ai bug off-by-one in lo/hi e all'overflow di interi in alcuni linguaggi (usa lo + (hi-lo)//2).
Dimezzare lo spazio di ricerca trasforma una ricerca su un milione di elementi in circa 20 confronti.
Il pattern divide-and-conquer dietro di essa riappare in alberi, database e innumerevoli problemi di intervista.
Conoscere il suo unico requisito rigoroso — input ordinato — ti protegge da un classico bug subdolo.