Miten binäärihaku toimii ja mitä se edellyttää?

Question

Accepted Answer

**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. ## Idea 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ä. ## Esimerkki ```python 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 ``` ## Jäljitys ```text 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 ``` ## Kompleksisuus - **Aika:** O(log n). **Tila:** O(1) iteratiivisesti. ## Sudenkuopat **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`). ## Miksi sillä on merkitystä 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ä.