Walk me through how binary search works, what its prerequisite is, and one subtle bug people introduce when they compute the midpoint.
technical-conceptual · Junior level · software-engineering
What the interviewer is really asking
Tests whether the candidate can explain binary search's halving mechanic, knows the sorted-input prerequisite, and is aware of the classic integer-overflow midpoint bug and its fix.
What to say
- Describe the mechanic: keep a low and high bound, compare the target to the middle element, and discard the half that can't contain it, so each step halves the search space — O(log n) time, O(1) space.
- State the hard prerequisite: the array must be sorted, because binary search relies on the invariant that everything left of the midpoint is smaller and everything right is larger; on unsorted data it's simply wrong.
- Name the midpoint bug and its fix: computing `mid = (low + high) / 2` can overflow a fixed-width integer when low and high are both large, so use `mid = low + (high - low) / 2`, which never sums two big numbers.
What to avoid
- Describe binary search without mentioning it requires sorted input — that's the prerequisite the whole method depends on.
- Claim it's O(n) or confuse it with linear search, missing that each comparison eliminates half the remaining candidates.
- Get the loop boundary wrong — an off-by-one on whether the loop is `low <= high` or `low < high`, or forgetting to move past the midpoint, which causes an infinite loop or a missed element.
Example answers
Strong: I keep two bounds, low and high. Each step I look at the middle element: if it equals the target I'm done, if the target is smaller I move high to mid-1, otherwise I move low to mid+1. Halving each step makes it O(log n) — a million-element sorted array is about 20 comparisons. The prerequisite is that the array is sorted, because the whole method depends on knowing which half the target must be in. The subtle bug I watch for is the midpoint: `(low + high) / 2` can overflow on large indices, so I write `low + (high - low) / 2` instead.
Weak: I look at the middle element and go left or right depending on the target — it's faster than checking everything. I don't think the array has to be sorted, you just split it in half each time.