Kako deluje binarno iskanje in kaj zahteva?

Question

Accepted Answer

**Binarno iskanje** najde tarčo v **sortirani** matriki z večkratnim razpolovitvijo območja iskanja. Vsaka primerjava izloči polovico preostalih elementov, kar daje **O(log n)** čas. ## Ideja Pogledam srednji element. Če je enak tarči, je narejeno. Če je tarča manjša, iščem levo polovico; če je večja, iščem desno polovico. Ponavljam, dokler ne najdem ali je območje prazno. ## Primer ```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 ``` ## Sledenje ```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 ``` ## Kompleksnost - **Čas:** O(log n). **Prostor:** O(1) iterativno. ## Pasti **Vhod mora biti sortiran** — sicer so rezultati nesmiselni. Pazite na napake za ena pri `lo`/`hi` in integer overflow v nekaterih jezikih (uporabite `lo + (hi-lo)//2`). ## Zakaj je to pomembno Razpolovljenje območja iskanja spremeni iskanje v matriki z milijonom elementov v ~20 primerjav. Vzorec deli-in-vladaj, ki je za tem, se znova pojavi v drevesih, bazah podatkov in nešteto intervjujih. Znanje njegove ene toge zahteve — sortiranega vhoda — vas varuje pred klasično subtilno napako.