Given a sorted array, how do you find a target in O(log n), and what are the two most common bugs?

How to answer

Binary search: keep a [lo, hi] window, compute mid = lo + (hi − lo)/2, compare a[mid] to the target, and discard half each step, giving O(log n) time and O(1) space. Common bugs: (1) mid = (lo + hi)/2 can overflow fixed-width integers — use lo + (hi − lo)/2; (2) inconsistent boundaries — mismatching the loop test (lo < hi vs lo ≤ hi) with the update (hi = mid vs hi = mid − 1) causes infinite loops or a missed endpoint.

Key idea: Halve the search space each step; watch integer overflow in mid and the loop boundary/update pairing.