Binary Search on Answer

Learning Outcome

Convert minimize-the-maximum and maximize-the-minimum problems into monotonic feasibility checks.

Pattern Recognition

Item	Detail
Core signal	The answer is a number and if x works, then every larger or smaller value also works.
Use when	You can write a deterministic check(candidate) with a true/false boundary.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

You are not searching the array; you are searching the answer space and using feasibility to discard half.

Exact Practice Question Names

Koko Eating Bananas
Capacity to Ship Packages Within D Days
Split Array Largest Sum
Minimize Max Distance to Gas Station
Maximum Length Possible by Cutting Woods

Interview Approach

Choose low/high bounds that definitely contain the answer.
Write a monotonic helper.
For minimum feasible answer, move high to mid when feasible.
For maximum feasible answer, move low upward when feasible.
Return the boundary value.

Pseudocode

low = smallest_possible
high = largest_possible
while low < high:
  mid = low + (high - low) // 2
  if feasible(mid):
    high = mid
  else:
    low = mid + 1
return low

Sample Dry Run

For shipping capacity, capacity 15 may need too many days, capacity 18 may fit, so the first feasible capacity lies between them and the search keeps tightening.

Edge Cases

low bound too small or high bound too small
Integer division rounding
Floating answer precision
Helper not monotonic

Common Mistakes

Binary searching indices instead of answers
Returning mid after the loop instead of the boundary
Using end = mid
- 1 in a first-true template

Complexity

Item	Detail
Expected time	O(n log range) for integer answers; O(n log precision) for floating answers.
Expected space	O(1) unless the helper builds extra state.

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.