Piye cara binary search gumana lan apa sing dibutuhake?

Question

Accepted Answer

**Binary search** golek target ing array sing **disortir** kanthi nggawe search range bola-bali. Saben perbandingan ngilangke separo saka elemen sing isih ana, menehi wektu **O(log n)**. ## Ide Padha tengah elemen. Yen padha karo target, rampung. Yen target luwih cilik, goleki sisih kiwa; yen luwih gedhe, goleki sisih tengen. Balekno nganti ketemu utawa range kosong. ## Conto ```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 ``` ## Jejak ```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 ``` ## Kompleksitas - **Wektu:** O(log n). **Spasi:** O(1) iteratif. ## Jebakan **Input kudu disortir** — salawane asil ora ana teges. Ati-ati bug off-by-one ing `lo`/`hi` lan integer overflow ing sawetara basa (gunakake `lo + (hi-lo)//2`). ## Mulane Penting Nggawe search space setengah ngowahi pencarian siji yuta elemen dadi kira-kira 20 perbandingan. Pola divide-and-conquer sastra mengko tampil maneh ing wit, database, lan akeh banget masalah wawancara. Ngewangi siji requirement sing kerep — input sing disortir — njaga sampeyan saka bug halus klasik.