Kako binarno pretraživanje funkcionira i što ga zahtijeva?

Question

IT Interview Practice · Accepted Answer

**Binary search** nalazi metu u **sortiranom** nizu ponovljenim razpolovljenjem raspona pretraživanja. Svaka usporedba eliminira polovicu preostalih elemenata, dajući **O(log n)** vrijeme. ## Ideja Pogledajte srednji element. Ako je jednak meti, gotovo. Ako je meta manja, pretražite lijevu polovicu; ako je veća, pretražite desnu polovicu. Ponavljajte dok se ne nađe ili dok raspon nije prazan. ## Primjer ```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 ``` ## Praćenje ```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 ``` ## Složenost - **Vrijeme:** O(log n). **Prostor:** O(1) iterativno. ## Zamke **Ulaz mora biti sortiran** — inače su rezultati besmisleni. Pazite na greške za jedan u `lo`/`hi` i integer overflow u nekim jezicima (koristite `lo + (hi-lo)//2`). ## Zašto je to važno Poljeravanje prostora pretraživanja pretvara pretraživanje s milion elemenata u ~20 usporedbi. Uzorak podijeli-pa-vladaj iza njega ponovno se pojavljuje u stablima, bazama podataka i bezbroj problema iz razgovora. Znanje njegovog jednog stroga zahtjeva — sortiranog ulaza — čuva vas od klasične suptilne greške.

Ideja

Primjer

Praćenje

Složenost

Zamke

Zašto je to važno

Povezana pitanja