You learned binary search to find a number in a sorted list. Now the twist that makes it an interview superpower: use binary search to find the answer itself. The smallest speed, the least capacity, the minimum days. This is binary search on the answer, and it's behind famous problems like Koko Eating Bananas.
The 12 interview patterns: you are here
- 1Two Pointerssorted + pair
- 2Sliding Windowcontiguous subarray
- 3Prefix Sum + Hash Maprange sums, sum = K
- 4Binary Search on Answersmallest value that works
- 5Fast & Slow Pointerscycle, middle
- 6Merge Intervalsoverlapping ranges
- 7Monotonic Stackcoming soon
- 8Heap / Top-Kcoming soon
- 9Tree Patternscoming soon
- 10Grid BFS & Topological Sortcoming soon
- 11Backtrackingcoming soon
- 12DP Patternscoming soon
The geyser story
You're setting the geyser for a bath. 20° is too cold. 30° is too cold. 40° is warm enough, and so is every setting above 40°. You want the lowest setting that works (to save electricity).
You don't try 20, 21, 22… one by one. You try the middle, and if it works you try lower, if it doesn't you try higher. Every check throws away half the settings. That's the whole idea.
Raju's ladoo challenge
This is the famous Koko Eating Bananas problem, with ladoos. Try a few speeds yourself, then press Run binary search:
🍬 Raju's ladoo challenge: the slowest speed that still finishes
Total 15 hours → NO, too slow (more than 8).
Every speed: NO or YES?
Notice the shape: all NOs first, then all YESes. That “sorted” line is what lets us binary search.
Now let binary search do it: it only checks the middle speed and throws away half each time.
Raju has 4 boxes of ladoos (3, 6, 7, 11) and 8 hours before guests arrive. Each hour he picks one box and eats up to “speed” ladoos from it. Eating fast makes him sick, so he wants the smallest speed that finishes in time.
The key insight: answers are sorted too
The boxes aren't sorted. That doesn't matter. What's sorted is the line of answers: speeds 1, 2, 3 say NO, and from 4 onwards every speed says YES. A faster speed can never take longer. Any time you see that “once it works, bigger always works” shape, you can binary search it.
🔍 Use binary search on the answer when you see
- ✓“Minimum speed / capacity / time / days such that…”
- ✓“Minimize the maximum” or “maximize the minimum”
- ✓You can easily check a guess in one pass
- ✓Once a value works, every bigger (or smaller) one works too
🚫 Don't use it when
- ✗There's no YES/NO check you can write
- ✗Answers jump around (works at 5, fails at 6, works at 7)
- ✗A direct formula or a single pass already gives the answer
The template (find the first YES)
low, high = smallest_possible, largest_possible
while low < high:
mid = (low + high) // 2
if works(mid): high = mid # YES: keep it, try smaller
else: low = mid + 1 # NO: go bigger
return low # first value that works⚡ Memory tricks
- 1
“Guess → Check → Halve”
The three moves of every binary-search-on-answer solution.
- 2
“NO NO NO YES YES”
Draw this line. If the answers look like it, binary search works.
- 3
“YES? Keep it, go left. NO? Drop it, go right.”
high = mid on YES, low = mid + 1 on NO.
- 4
“Minimize the max = binary search”
The strongest signal phrase in interview questions.
Code: Koko Eating Bananas and integer square root
Two problems, one template. In square root we want the last YES (largest x with x² ≤ n), so the moves are mirrored. Outputs in the comments are real.
def hours_needed(piles, speed):
"""Hours to eat every pile at `speed` bananas/hour (one pile per hour max)."""
return sum((p + speed - 1) // speed for p in piles) # ceil(p / speed)
def min_eating_speed(piles, h):
"""Smallest speed that finishes within h hours."""
low, high = 1, max(piles) # the answer is somewhere in this range
while low < high:
mid = (low + high) // 2 # guess a speed
if hours_needed(piles, mid) <= h:
high = mid # works: try slower (keep mid, it might be the answer)
else:
low = mid + 1 # too slow: go faster
return low
def int_sqrt(n):
"""Largest x with x * x <= n, using the same guess-and-check idea."""
low, high = 0, n
while low < high:
mid = (low + high + 1) // 2 # round up so the loop always shrinks
if mid * mid <= n:
low = mid # mid works: answer is mid or bigger
else:
high = mid - 1
return low
print(min_eating_speed([3, 6, 7, 11], 8)) # 4
print(hours_needed([3, 6, 7, 11], 4)) # 8 (1 + 2 + 2 + 3)
print(hours_needed([3, 6, 7, 11], 3)) # 10 (too slow)
print(int_sqrt(40)) # 6One pattern, many problems
| Famous problem | How the pattern solves it | Level |
|---|---|---|
| Sqrt(x) | Largest x with x² ≤ n | Easy |
| Koko Eating Bananas | Smallest speed with hours ≤ h | Medium |
| Capacity to Ship Packages Within D Days | Smallest capacity that needs ≤ D days | Medium |
| Minimum Number of Days to Make m Bouquets | Smallest day where m bouquets are possible | Medium |
| Find the Smallest Divisor Given a Threshold | Smallest divisor with sum ≤ threshold | Medium |
| Aggressive Cows / Magnetic Force | Largest minimum distance (maximize the min) | Medium |
| Split Array Largest Sum | Smallest possible largest part (minimize the max) | Hard |
🎯 Spot the pattern: is it binary search on the answer?
In an interview nobody tells you the pattern. Read each problem and decide. Look for the signal words.
1. Find the minimum ship capacity to deliver all packages within D days.
2. Find the integer square root of n without using sqrt().
3. Find the longest substring with at most 2 distinct characters.
4. Split an array into k parts so the largest part-sum is as small as possible.
5. Count subarrays with sum exactly K.
🧠 PATH memory card
Remember binary search on the answer for good
Picture it · Anchor it · Trace it · Hit-recall it. Four quick steps that turn “I read it once” into “I can explain it in an exam”.
- P
Picture it
Your brain remembers scenes far better than definitions.
← swipe to see the whole picture →
Geyser settings: too cold, too cold, just right, and every setting above also works. Find the lowest one that works by always trying the middle.
- A
Anchor it
A silly sentence you can't forget, where every word maps to the concept.
“Geyser: Guess, Check, Halve (NO NO NO YES YES)”
- Geyser→A range of possible answers, low to high
- Guess→mid = (low + high) // 2
- Check→works(mid): a simple one-pass test
- Halve→YES → high = mid · NO → low = mid + 1
- NO NO NO YES YES→Answers must be monotonic for this to work
- T
Trace it
Run it by hand on a tiny example once. Doing beats reading.
Boxes[3, 6, 7, 11], 8 hours. Range 1–11 → try 6: 6h YES → range 1–6 → try 3: 10h NO → range 4–6 → try 5: 8h YES → range 4–5 → try 4: 8h YES → low = high = 4. Four checks instead of eleven. - H
Hit-recall it
Test yourself now, then again on the day each card comes back.
Card 1 / 7 · new0 mastered · 0 practisedSay the answer out loud first, then flip and be honest.
Common mistakes
- Wrong range. Low must be a value that could work (often 1) and high one that surely works (like the biggest pile).
- Using
high = mid − 1on YES. You might throw away the answer. Keep mid. - Integer overflow in the check. In Java/C++, sums of hours or capacities can exceed int: use
long.
Where to go next
Four array patterns done. The next one moves to linked lists, with a famous race between a tortoise and a hare that detects loops and finds the middle in one pass: fast and slow pointers.
Key takeaways
- ✓Search the range of possible answers, not the input.
- ✓Works when answers are monotonic: NO NO NO YES YES.
- ✓Guess the middle, check it in one pass, halve the range.
- ✓First YES: high = mid on YES, low = mid + 1 on NO.
- ✓Signals: minimum … such that, minimize the maximum, maximize the minimum.
Frequently asked questions
What is binary search on the answer?
Instead of searching for an item in a sorted list, you search over all possible answers (like speeds 1 to 1,000,000) for the smallest or largest one that works. It works whenever the answers are monotonic: once one value works, every bigger value also works (or every smaller one).
How do I recognise a binary search on answer problem?
Look for 'minimum speed / capacity / time / days such that…', 'minimize the maximum' or 'maximize the minimum', and a check that's easy to write: given a guess, can I tell in one pass whether it works? If yes and the answers go NO NO NO YES YES YES, binary search the answer.
How do I solve Koko Eating Bananas?
The answer (eating speed) lies between 1 and the biggest pile. For a guessed speed, hours = sum of ceil(pile / speed). If hours ≤ h, the speed works, so try slower (high = mid). Otherwise go faster (low = mid + 1). When low meets high, that's the minimum speed. Time: O(n log max).
What is the time complexity of binary search on the answer?
O(log R) guesses, where R is the size of the answer range, times the cost of one check, often O(n). So typically O(n log R). For Koko Eating Bananas that's O(n log m), where m is the largest pile.
Why use while (low < high) and high = mid here?
Because we're looking for the first value that works, and mid itself might be that value, so we can't throw it away (high = mid, not mid − 1). The loop ends when low == high, which is the answer. This 'find the first YES' form avoids most off-by-one bugs.
🧠 Quick check: binary search on the answer
1. What must be true to binary search on the answer?
2. Speed 6 works (finishes in time). What can you conclude?
3. Boxes [3, 6, 7, 11], speed 4. How many hours?
4. The guess works. In “find the first YES”, what do you set?
Checking your access…