Binäärihaku löytää kohteen järjestetystä taulukosta puolittamalla hakualueen toistuvasti. Jokainen vertailu eliminoi puolet jäljellä olevista elementeistä, mikä antaa O(log n) aikakompleksisuuden.
Katsotaan keskimmäistä elementtiä. Jos se vastaa kohdetta, valmis. Jos kohde on pienempi, haetaan vasemmasta puoliskosta; jos suurempi, haetaan oikeasta puoliskosta. Toistetaan kunnes kohde löytyy tai alue on tyhjä.
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
Syöte täytyy olla järjestetty — muutoin tulokset ovat merkityksettömiä. Varokaa off-by-one-virheitä lo/hi-muuttujissa ja kokonaisluvun ylivuotoa joissakin kielissä (käytä lo + (hi-lo)//2).
Hakualueen puolittaminen muuttaa miljoonan elementin haun noin 20 vertailuun.
Taustalla oleva jakaa-ja-hallitse-malli ilmaantuu uudelleen puissa, tietokannoissa ja lukemattomissa haastattelutehtävissä.
Yksi sen vaikeimmista vaatimuksista tunteminen — järjestetty syöte — pitää sinut erossa klassisesta hienovaraisesta virheestä.
Kirjasto IT-haastattelukysymyksiä yksityiskohtaisine vastauksineen — Juniorista Senioriin.
Lahjoita