Binary search finner et mål i en sortert array ved gjentatte ganger å halvere søkeområdet. Hver sammenligning eliminerer halvparten av de gjenværende elementene, noe som gir O(log n) tid.
Se på det midterste elementet. Hvis det er lik målet, er du ferdig. Hvis målet er mindre, søk i den venstre halvdelen; hvis større, søk i den høyre halvdelen. Gjenta til du finner det eller området er tomt.
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
Inngangen må være sortert — ellers er resultatene meningsløse. Vær forsiktig med off-by-one feil i lo/hi og heltallsoverflow i noen språk (bruk lo + (hi-lo)//2).
Å halvere søkeområdet gjør at et søk blant en million elementer blir ~20 sammenligninger.
Divide-and-conquer mønsteret bak det dukker opp igjen i trær, databaser og utallige intervjuspørsmål.
Å kjenne dens ene harde krav — sortert inngang — holder deg unna en klassisk subtil feil.