Binary Search on Answer
The Intuition
Imagine you need to drive to the airport, and you're wondering "what's the minimum speed I need to maintain to arrive by 3pm?" You don't test every speed from 1 mph to 200 mph one by one. You pick a middle value, say 100. At that speed, would you arrive in time? Yes, easily. Okay, try 50. Still on time? Yes. Try 25. Too slow, you'd be late. Try 37. Still late. Try 43. Just barely on time. You zero in on the answer through halving, not exhaustive testing.
Notice what you're searching for here. You're not looking through an array for an element. You're searching for a number, a speed, that lives on a continuous number line. Everything above some threshold works. Everything below it fails. That boundary between "too slow" and "fast enough" is your answer, and binary search finds boundaries in O(log n) guesses.
The key insight is the monotonic property. Picture the number line of all possible speeds laid out left to right. Under each speed, write whether you'd arrive on time:
10 mph: NO | 20: NO | 30: NO | 37: NO | 43: YES | 50: YES | 60: YES | 100: YES
See the pattern? It goes NO, NO, NO, ..., YES, YES, YES forever. The answers flip from false to true at some point and stay true. That is the monotonic property. If driving at 43 mph gets you there on time, then 44 definitely does too, and 50, and 100. If 37 makes you late, then 30 and 20 and 10 also make you late. There is a single flip point, and binary search finds it in O(log n) guesses.
This is what separates "binary search on answer" from regular binary search. In regular binary search, you are looking for a specific value in a sorted array. Here, you are looking for the boundary where a condition flips. You do not even need a sorted array. You just need a yes/no function whose answers form that clean NO-to-YES (or YES-to-NO) boundary across the candidate values.
Your feasibility function is the heart of each problem. For Koko eating bananas, it checks "can she finish all piles at speed k within h hours?" For splitting an array, it checks "can I split into m groups where no group exceeds sum mid?" You write one function that takes a candidate answer and returns yes or no, then let binary search find the tightest candidate that still returns yes.
The problem asks you to minimize a maximum value or maximize a minimum value, and you can write a feasibility function that is monotonic over the candidate range. If a candidate value works, then all larger (or all smaller) values also work.
Condition is not monotonic (no clear boundary), answer space is discrete and small (just try all), or need to find multiple answers not just the boundary.
Variations:
- Minimize the maximum: Use
is_feasibleto check if you can achieve the goal with a value at mostmid. If yes, search lower. - Maximize the minimum: Use
is_feasibleto check if you can achieve the goal with a value at leastmid. If yes, search higher. - Floating-point answer: Replace the while condition with a fixed iteration count (e.g., 100 iterations) or an epsilon check.
- All elements are equal, making the answer trivially the element value itself
- Only one element exists, so the answer is forced
- The feasibility boundary sits at the very start or end of the search range
- Large input values that require careful overflow handling when computing
lo + (hi - lo) / 2 - Floating-point variants where you need sufficient iterations for precision
Key Points
- •Binary search over the value space, not the index space
- •Define a feasibility function that checks if a candidate answer is valid
- •Identify the monotonic property: if x works, all values above (or below) also work
- •Search boundaries are the minimum and maximum possible answer values
- •Works when the problem asks to minimize the maximum or maximize the minimum
Code Template
1 def binary_search_on_answer(nums, condition_args):
2 """Binary search on the answer (value space).
3 Finds the minimum value that satisfies the condition."""
4
5 def is_feasible(candidate):
6 # Check whether 'candidate' is a valid answer.
7 # This function must be monotonic:
8 # if feasible(x) is True, then feasible(x+1) is also True.
9 pass # problem-specific logic
10
11 lo, hi = min_possible, max_possible
12
13 while lo < hi:
14 mid = lo + (hi - lo) // 2
15 if is_feasible(mid):
16 hi = mid # candidate works, try smaller
17 else:
18 lo = mid + 1 # candidate fails, need larger
19
20 return lo
21
22 # Example: Koko eating bananas
23 def min_eating_speed(piles, h):
24 """Find minimum speed k so Koko finishes in h hours."""
25 import math
26
27 def can_finish(k):
28 hours = sum(math.ceil(p / k) for p in piles)
29 return hours <= h
30
31 lo, hi = 1, max(piles)
32
33 while lo < hi:
34 mid = lo + (hi - lo) // 2
35 if can_finish(mid):
36 hi = mid
37 else:
38 lo = mid + 1
39
40 return loCommon Mistakes
- Setting incorrect search boundaries (lo and hi)
- Getting the feasibility check logic inverted
- Off-by-one errors when deciding between lo = mid vs lo = mid + 1
- Forgetting that the feasibility function must be monotonic over the search space