Binary search on answer is one of the most powerful and elegant problem-solving techniques in competitive programming and technical interviews. It transforms seemingly intractable optimization problems into efficient O(n log m) solutions.
But here's what makes it challenging: there's no explicit sorted array. Instead, you're searching on an answer space—a range of possible solutions—using a "guess and check" approach. Once you master this pattern, you'll unlock an entire class of problems that would otherwise seem impossible.
This comprehensive guide will teach you everything about binary search on answer: when to use it, how to identify the answer space, how to design feasibility functions, and complete templates for both "minimize maximum" and "maximize minimum" problems.
Use binary search on answer when:
Template:
def binary_search_on_answer(min_val, max_val, is_feasible):
left, right = min_val, max_val
result = max_val
while left <= right:
mid = left + (right - left) // 2
if is_feasible(mid):
result = mid
right = mid - 1 # Try smaller for "minimize"
else:
left = mid + 1
return resultTime: O(log(max - min) × feasibility_check_time)
Binary search on answer is a technique where you binary search on the range of possible answers rather than on an array of elements. You repeatedly "guess" a candidate answer and check if it's feasible.
The fundamental idea: If you can verify whether a candidate answer works, and feasibility is monotonic (if answer x works, then x+1 also works OR x-1 also works), you can binary search for the optimal answer.
Example:
Problem: Koko Eating Bananas
Piles: [3, 6, 7, 11], Hours: 8
Question: What's the minimum eating speed to finish all bananas?
Answer space: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Feasibility: F F F T T T T T T T T
↑
Find first T (minimum feasible speed)
Speed 1: 3+6+7+11 = 27 hours > 8 ✗
Speed 2: 2+3+4+6 = 15 hours > 8 ✗
Speed 3: 1+2+3+4 = 10 hours > 8 ✗
Speed 4: 1+2+2+3 = 8 hours ≤ 8 ✓ (Answer!)Classic binary search:
Binary search on answer:
The pattern follows three steps:
Visual representation:
Answer Space: [min ..................... max]
Feasibility: [F F F F F T T T T T T T T T T]
↑
Find this boundary
Binary search finds the boundary between feasible and infeasibleUse binary search on answer when you see these keywords:
✅ "Minimize the maximum"
✅ "Maximize the minimum"
✅ "Find the smallest/largest value such that..."
✅ Optimization with constraints
Binary search on answer requires:
Example check:
Problem: Koko Eating Bananas
1. Answer range? ✓
- Min: 1 banana/hour (slowest possible)
- Max: max(piles) (eat entire largest pile in 1 hour)
2. Feasibility check? ✓
- Given speed k, calculate hours = sum(ceil(pile/k))
- Check if hours <= h
3. Monotonicity? ✓
- If speed k works, any speed > k also works
- We want minimum, so search for smallest feasible kQuestion 1: Does the problem ask for optimization?
├─ "Minimize maximum" or "Maximize minimum" → Continue
└─ Just "find" or "search" → Classic binary search
Question 2: Is there a clear answer range?
├─ Yes, I can define [min, max] → Continue
└─ No → Binary search on answer won't work
Question 3: Can I check if a candidate answer works?
├─ Yes, I can write is_feasible(x) → Continue
└─ No → Need different approach
Question 4: Is feasibility monotonic?
├─ If x works, does x+1 work? (or x-1?) → Binary search on answer ✓
└─ No monotonicity → Need exhaustive searchdef binary_search_on_answer(min_answer, max_answer, is_feasible, minimize=True):
"""
Template for binary search on answer.
Args:
min_answer: Minimum possible answer
max_answer: Maximum possible answer
is_feasible: Function that checks if a candidate answer works
minimize: True for "minimize maximum", False for "maximize minimum"
Returns:
Optimal answer
Time: O(log(max - min) × feasibility_check_time)
Space: O(1)
"""
left, right = min_answer, max_answer
result = max_answer if minimize else min_answer
while left <= right:
mid = left + (right - left) // 2
if is_feasible(mid):
result = mid
if minimize:
# Try to find smaller feasible answer
right = mid - 1
else:
# Try to find larger feasible answer
left = mid + 1
else:
if minimize:
# Need larger answer
left = mid + 1
else:
# Need smaller answer
right = mid - 1
return resultfunction binarySearchOnAnswer(minAnswer, maxAnswer, isFeasible, minimize = true) {
let left = minAnswer;
let right = maxAnswer;
let result = minimize ? maxAnswer : minAnswer;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (isFeasible(mid)) {
result = mid;
if (minimize) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (minimize) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return result;
}public int binarySearchOnAnswer(int minAnswer, int maxAnswer,
Predicate<Integer> isFeasible,
boolean minimize) {
int left = minAnswer;
int right = maxAnswer;
int result = minimize ? maxAnswer : minAnswer;
while (left <= right) {
int mid = left + (right - left) / 2;
if (isFeasible.test(mid)) {
result = mid;
if (minimize) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (minimize) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return result;
}Problem statement: Koko has piles of bananas. She can eat at most k bananas per hour. Find the minimum k such that she can finish all bananas within h hours.
Solution:
def minEatingSpeed(piles: List[int], h: int) -> int:
"""
Find minimum eating speed to finish all bananas in h hours
Time: O(n log m) where m = max(piles)
Space: O(1)
"""
def can_finish(speed):
"""Check if Koko can finish with given speed"""
hours = 0
for pile in piles:
# Ceiling division: how many hours for this pile
hours += (pile + speed - 1) // speed
return hours <= h
# Answer space: [1, max(piles)]
# Min: 1 banana/hour (slowest)
# Max: max(piles) (eat largest pile in 1 hour)
return binary_search_on_answer(1, max(piles), can_finish, minimize=True)
# Example
print(minEatingSpeed([3, 6, 7, 11], 8)) # 4
# Speed 4: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1+2+2+3 = 8 ✓Why it works:
can_finish(k) == TrueStep-by-step trace:
Piles: [3, 6, 7, 11], h = 8
left=1, right=11, mid=6
can_finish(6)? 1+1+2+2=6 ≤ 8 ✓
result=6, try smaller: right=5
left=1, right=5, mid=3
can_finish(3)? 1+2+3+4=10 > 8 ✗
Need larger: left=4
left=4, right=5, mid=4
can_finish(4)? 1+2+2+3=8 ≤ 8 ✓
result=4, try smaller: right=3
left=4, right=3 → stop
Answer: 4Problem statement: Ship packages within d days. Each day, load packages in order up to ship capacity. Find minimum capacity.
Solution:
def shipWithinDays(weights: List[int], days: int) -> int:
"""
Find minimum ship capacity to ship all packages in given days
Time: O(n log(sum - max))
Space: O(1)
"""
def can_ship(capacity):
"""Check if we can ship with given capacity"""
days_needed = 1
current_load = 0
for weight in weights:
if current_load + weight > capacity:
# Start new day
days_needed += 1
current_load = weight
else:
current_load += weight
return days_needed <= days
# Answer space: [max(weights), sum(weights)]
# Min: max(weights) (must fit largest package)
# Max: sum(weights) (ship everything in 1 day)
return binary_search_on_answer(max(weights), sum(weights), can_ship)
# Example
print(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) # 15Why it works:
Problem statement: Split array into m subarrays. Minimize the largest sum among these subarrays.
Solution:
def splitArray(nums: List[int], m: int) -> int:
"""
Split array into m subarrays, minimize largest sum
Time: O(n log(sum - max))
Space: O(1)
"""
def can_split(max_sum):
"""Check if we can split into m subarrays with max sum"""
subarrays = 1
current_sum = 0
for num in nums:
if current_sum + num > max_sum:
# Start new subarray
subarrays += 1
current_sum = num
else:
current_sum += num
return subarrays <= m
# Answer space: [max(nums), sum(nums)]
# Min: max(nums) (each element in its own subarray)
# Max: sum(nums) (all elements in one subarray)
return binary_search_on_answer(max(nums), sum(nums), can_split)
# Example
print(splitArray([7, 2, 5, 10, 8], 2)) # 18
# Split: [7, 2, 5] (sum=14) and [10, 8] (sum=18), max=18Problem statement: Place m balls in n positions to maximize the minimum distance between any two balls.
Solution:
def maxDistance(position: List[int], m: int) -> int:
"""
Maximize minimum distance between m balls
Time: O(n log n + n log(max - min))
Space: O(1)
"""
position.sort()
def can_place(min_dist):
"""Check if we can place m balls with minimum distance"""
count = 1 # Place first ball at position[0]
last_pos = position[0]
for pos in position[1:]:
if pos - last_pos >= min_dist:
count += 1
last_pos = pos
if count == m:
return True
return count >= m
# Answer space: [1, position[-1] - position[0]]
# Min: 1 (minimum possible distance)
# Max: max distance between first and last position
return binary_search_on_answer(
1,
position[-1] - position[0],
can_place,
minimize=False # Maximize
)
# Example
print(maxDistance([1, 2, 3, 4, 7], 3)) # 3
# Place at positions 1, 4, 7: distances are 3, 3Why it works:
Problem statement: Place c cows in n stalls to maximize the minimum distance between any two cows.
Solution:
def aggressive_cows(stalls: List[int], cows: int) -> int:
"""
Maximize minimum distance between cows
Time: O(n log n + n log(max - min))
Space: O(1)
"""
stalls.sort()
def can_place(min_dist):
"""Check if we can place cows with minimum distance"""
count = 1
last_pos = stalls[0]
for stall in stalls[1:]:
if stall - last_pos >= min_dist:
count += 1
last_pos = stall
if count == cows:
return True
return False
return binary_search_on_answer(
1,
stalls[-1] - stalls[0],
can_place,
minimize=False
)
# Example
print(aggressive_cows([1, 2, 4, 8, 9], 3)) # 3
# Place at 1, 4, 8: distances are 3, 4Common patterns:
Example:
Koko Eating Bananas:
Min speed = 1 (slowest possible)
Ship Packages:
Min capacity = max(weights) (must fit largest package)
Magnetic Force:
Min distance = 1 (minimum possible distance)Common patterns:
Example:
Koko Eating Bananas:
Max speed = max(piles) (eat largest pile in 1 hour)
Ship Packages:
Max capacity = sum(weights) (ship everything in 1 day)
Magnetic Force:
Max distance = position[-1] - position[0]For "minimize maximum":
For "maximize minimum":
Example:
Koko Eating Bananas (minimize maximum):
If speed 5 works, does speed 6 work? YES (faster is always ok)
Monotonicity: [F F F F T T T T T T T]
↑ find first T
Magnetic Force (maximize minimum):
If distance 3 works, does distance 2 work? YES (smaller is easier)
Monotonicity: [T T T T T F F F F F F]
↑ find last TEvery feasibility function has:
Template:
def is_feasible(candidate_answer):
# 1. Initialize
counter = initial_value
# 2. Iterate
for item in data:
# Update counter based on candidate_answer
counter = update(counter, item, candidate_answer)
# 3. Check constraint
return counter meets_constraintPattern 1: Counting (Koko Eating Bananas)
def can_finish(speed):
hours = 0
for pile in piles:
hours += (pile + speed - 1) // speed # Ceiling division
return hours <= hPattern 2: Greedy Grouping (Ship Packages)
def can_ship(capacity):
days = 1
current_load = 0
for weight in weights:
if current_load + weight > capacity:
days += 1
current_load = weight
else:
current_load += weight
return days <= max_daysPattern 3: Greedy Placement (Magnetic Force)
def can_place(min_dist):
count = 1
last_pos = positions[0]
for pos in positions[1:]:
if pos - last_pos >= min_dist:
count += 1
last_pos = pos
return count >= mMistake 1: Wrong Monotonicity Direction
❌ Wrong:
# For "minimize maximum", checking if we can do BETTER than mid
if is_feasible(mid):
left = mid + 1 # WRONG: should try smaller✅ Correct:
if is_feasible(mid):
result = mid
right = mid - 1 # Try smaller for minimizeSee guide: Feasibility Function Mistakes
Mistake 2: Off-by-One in Counting
❌ Wrong:
hours += pile // speed # WRONG: doesn't handle remainder✅ Correct:
hours += (pile + speed - 1) // speed # Ceiling division
# Or: hours += math.ceil(pile / speed)Mistake 3: Incorrect Greedy Logic
❌ Wrong:
# Placing balls: forgetting to update last position
if pos - last_pos >= min_dist:
count += 1
# WRONG: didn't update last_pos✅ Correct:
if pos - last_pos >= min_dist:
count += 1
last_pos = pos # Update positionMaster binary search on answer with these problems:
Beginner:
Intermediate:
4. Split Array Largest Sum (#410) — Minimize maximum sum
5. Magnetic Force Between Two Balls (#1552) — Maximize minimum
6. Minimize Max Distance to Gas Station (#774) — Continuous answer space
7. Kth Smallest Element in Sorted Matrix (#378) — Count elements ≤ mid
Advanced:
8. Median of Two Sorted Arrays (#4) — Binary search on answer + partitioning
9. Minimize Max Distance to Gas Station (#774) — Floating point binary search
10. Cutting Ribbons (#1891) — Maximize with constraint
Time Complexity: O(log(max - min) × C)
Examples:
Space Complexity: O(1)
Q: How is this different from regular binary search?
A: Regular binary search searches in an explicit sorted array. Binary search on answer searches in an implicit answer space (range of possible solutions). The key is monotonic feasibility, not a sorted array.
Q: How do I know if feasibility is monotonic?
A: Ask: "If answer x works, does x+1 work (or x-1)?" If yes, it's monotonic. For "minimize maximum," larger values should work if smaller ones do. For "maximize minimum," smaller values should work if larger ones do.
Q: What if I can't determine the answer space?
A: Look for natural bounds:
Q: Can the answer space be floating point?
A: Yes! Use a precision threshold instead of left <= right:
while right - left > 1e-6:
mid = (left + right) / 2
if is_feasible(mid):
right = mid
else:
left = midQ: What if my feasibility check is O(n²)?
A: Binary search on answer will be O(n² log m), which may still be acceptable depending on constraints. Optimize the feasibility check if possible.
Binary search on answer is a powerful technique that transforms optimization problems into efficient logarithmic solutions. It's not about searching in arrays—it's about searching in answer spaces.
Key principles:
The template:
def solve(data, constraint):
def is_feasible(candidate):
# Check if candidate answer works
return check_constraint(candidate)
return binary_search_on_answer(min_val, max_val, is_feasible)When to use:
Master this pattern, and you'll solve dozens of LeetCode hard problems with confidence. For more patterns, see the Complete Binary Search Guide, Why Binary Search on Answer Works, and Minimize Maximum vs Maximize Minimum.
Next time you see "minimize the maximum" or "maximize the minimum," reach for binary search on answer.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free