How does binary search work, and what does it require?

Question

Accepted Answer

**Binary search** finds a target in a **sorted** array by repeatedly halving the search range. Each comparison eliminates half of the remaining elements, giving **O(log n)** time. ## The idea Look at the middle element. If it equals the target, done. If the target is smaller, search the left half; if larger, search the right half. Repeat until found or the range is empty. ## Example ```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 ``` ## Trace ```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 ``` ## Complexity - **Time:** O(log n). **Space:** O(1) iterative. ## Pitfalls The **input must be sorted** — otherwise results are meaningless. Watch off-by-one bugs in `lo`/`hi` and integer overflow in some languages (use `lo + (hi-lo)//2`). ## Why it matters Halving the search space turns a million-element lookup into ~20 comparisons. The divide-and-conquer pattern behind it reappears in trees, databases, and countless interview problems. Knowing its one hard requirement — sorted input — keeps you from a classic subtle bug.