Binary Search On Answer

What's being tested

Binary search on answer: recognizing when the value you need is not directly searchable in an array, but a monotonic predicate over possible answers is. Interviewers are probing whether you can define bounds, implement can(x) correctly, prove monotonicity, and handle edge cases without off-by-one bugs.

Patterns & templates

• Maximize feasible value — use while lo <= hi, move lo = mid + 1 when can(mid) is true; return hi.

• Minimize feasible value — move hi = mid - 1 when can(mid) is true; return lo as the smallest valid answer.

• Capacity partitioning — can(capacity) scans once, counting days/partitions; O(n log S) time, O(1) space, preserve input order.

• Piece-count feasibility — sum(length // x) >= k is monotonic decreasing as x grows; avoid testing x = 0.

• Value-space matrix search — count elements <= mid in O(n) from bottom-left/top-right; total O(n log range) time.

• Integer-safe midpoint — compute mid = lo + (hi - lo) // 2; in Python overflow is irrelevant, but still communicate the habit.

Common pitfalls

Pitfall: Confusing searching indices with searching answer values; the answer may not appear as an array element.

Pitfall: Using the wrong return value after convergence; for “minimum feasible,” return lo, for “maximum feasible,” usually return hi.

Pitfall: Weak bounds cause bugs: shipping lower bound is max(weights), ribbon lower bound is 1, matrix bounds are min/max values.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.