Binary Search On Answer
Asked of: Machine Learning Engineer
Last updated

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, movelo = mid + 1whencan(mid)is true; returnhi. -
Minimize feasible value — move
hi = mid - 1whencan(mid)is true; returnloas 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) >= kis monotonic decreasing asxgrows; avoid testingx = 0. -
Value-space matrix search — count elements
<= midinO(n)from bottom-left/top-right; totalO(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 returnhi.
Pitfall: Weak bounds cause bugs: shipping lower bound is
max(weights), ribbon lower bound is1, matrix bounds are min/max values.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- Binary Search And Feasibility OptimizationCoding & Algorithms
- Binary Search, Partitioning, And Convex SearchCoding & Algorithms
- Sliding Window, Binary Search, and Prefix ReasoningCoding & Algorithms
- Array Search, Selection, And Dynamic ProgrammingCoding & Algorithms
- BST Algorithms And Lowest Common AncestorCoding & Algorithms
- Dynamic Programming, Backtracking, And Combinatorial SearchCoding & Algorithms