Binary Search and the Art of Halving

Binary search looks like the smallest algorithm you know — and it's among the most failure-prone to implement and the most broadly applicable to generalize. Interviews exploit both facts.

The invariant discipline

The reason "a binary search that works on the first try" is a famous rarity: boundary management. Write it with an explicit invariant and it stops being fragile. One clean template — find the first index where a condition becomes true (the condition must be monotone: false…false, true…true):

lo, hi = 0, n          # answer lies in [lo, hi]
while lo < hi:
    mid = (lo + hi) // 2
    if condition(mid):
        hi = mid       # mid might be the answer
    else:
        lo = mid + 1   # mid is ruled out
return lo

Everything classic is a special case: exact lookup (condition = "a[i] >= target", then check equality), leftmost/rightmost duplicate, insertion point (bisect_left/bisect_right in Python — know they exist and differ). The two bugs interviewers watch for: mid computed so the loop can stall (hi = mid paired with mid = (lo+hi+1)//2 loops forever on two elements), and testing on arrays without the empty / single-element / all-true / all-false cases.

Binary search on the answer

The powerful generalization: the array is imaginary. If a question asks for a threshold value and the feasibility check is monotone — "could we do it with capacity $c$?" is false below some point and true above — then binary-search the answer space:

• Square roots without a calculator: bisect on $x^2 \le t$; each iteration adds a bit of precision, ~40 iterations for double precision.
• Minimum ship capacity to move packages in $D$ days, smallest max-page-count when splitting books among readers — the canonical interview family: greedily check feasibility at capacity $c$ ($O(n)$), bisect on $c$ ($O(\log \text{range})$).
• The quant flavor: implied volatility! Option price is monotone in σ, so "find the σ matching this market price" is bisection on the answer — the options course's inversion is literally this lesson's algorithm. (Production code uses Newton's method for speed, with bisection as the robust fallback — a good sentence to say.)

Halving beyond arrays

• Twenty questions / guess-my-number: each yes/no halves the space: $\lceil \log_2 n \rceil$ questions for $n$ candidates — 20 questions distinguish ~10⁶ items. This is the information-theory bound from the 8-balls question, base 2.
• Debugging by bisection: git bisect finds the offending commit among 1,024 in ten builds. Mentioning it in a "how would you find the regression?" system question lands well.
• Exponentiation by squaring: $x^n$ in $O(\log n)$ multiplies — the halving idea applied to computation itself.

The interview version

"A function is negative then positive over [0, 10⁹]. Find the crossing to within 10⁻⁶." — Bisection; iterations = $\log_2(10^9/10^{-6}) = \log_2 10^{15} \approx 50$. Being able to count the iterations — not just name the method — is the difference the question measures. Then the implementation follow-up wants the invariant template above, narrated: "lo is always ruled out, hi is always feasible, they meet at the answer." Say the invariant, and the off-by-ones take care of themselves.