Here’s a mind-bending insight: binary search doesn’t just work on sorted arrays. It works on any monotonic condition. If there’s a point where the answer flips from “no” to “yes” (or vice versa), we can binary search on it.
In simple language, instead of searching for a value in an array, we’re searching for the answer itself. We pick a candidate answer, check if it works, and narrow our search range based on the result. It’s binary search, but on the solution space.
The Key Insight
Traditional binary search: “Is the value at index mid our target?”
Binary search on answer: “Is mid a valid answer? If yes, can we do better?”
How to Recognize These Problems
Look for these phrases in the problem statement:
- “Minimize the maximum…” (e.g., minimize the maximum pages a student reads)
- “Maximize the minimum…” (e.g., maximize the minimum distance between cows)
- “What is the minimum speed/capacity/time to…”
- “Can we do X within Y constraint?” where Y is a number we can binary search on
The key pattern: there’s a monotonic relationship. If speed 5 works, speed 6 definitely works too. If speed 3 doesn’t work, speed 2 definitely doesn’t either.
The Template
Every binary search on answer problem follows this structure:
function binarySearchOnAnswer(input) {
let lo = /* minimum possible answer */;
let hi = /* maximum possible answer */;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (isFeasible(mid, input)) {
hi = mid; // mid works, try smaller (minimize)
} else {
lo = mid + 1; // mid doesn't work, need bigger
}
}
return lo; // lo === hi, the smallest feasible answer
}
function isFeasible(candidate, input) {
// check if 'candidate' is a valid answer
// this is the problem-specific part
}def binary_search_on_answer(input_data):
lo = 0 # minimum possible answer
hi = 10**9 # maximum possible answer
while lo < hi:
mid = (lo + hi) // 2
if is_feasible(mid, input_data):
hi = mid # mid works, try smaller (minimize)
else:
lo = mid + 1 # mid doesn't work, need bigger
return lo # lo == hi, the smallest feasible answer
def is_feasible(candidate, input_data):
# check if 'candidate' is a valid answer
pass # problem-specific logicstatic int binarySearchOnAnswer(int[] input) {
int lo = 0; // minimum possible answer
int hi = 1_000_000_000; // maximum possible answer
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isFeasible(mid, input)) {
hi = mid; // mid works, try smaller
} else {
lo = mid + 1; // mid doesn't work, need bigger
}
}
return lo;
}
static boolean isFeasible(int candidate, int[] input) {
// problem-specific check
return true;
}Two things to note: we write the isFeasible function separately (keeps it clean), and for “minimize” problems we do hi = mid, for “maximize” problems we do lo = mid.
Koko Eating Bananas
Koko has piles of bananas and h hours. She eats at speed k bananas/hour (one pile at a time, even if she finishes a pile early). Find the minimum k so she finishes in h hours (LeetCode #875).
Why binary search on answer? If she can finish at speed 5, she can definitely finish at speed 6. Monotonic condition! We binary search on the speed k.
function minEatingSpeed(piles, h) {
let lo = 1;
let hi = Math.max(...piles); // worst case: eat largest pile in 1 hr
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
// count hours needed at speed mid
const hours = piles.reduce(
(sum, p) => sum + Math.ceil(p / mid), 0
);
if (hours <= h) {
hi = mid; // can finish, try slower
} else {
lo = mid + 1; // too slow, need faster
}
}
return lo;
}
// minEatingSpeed([3,6,7,11], 8) => 4def min_eating_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
# count hours needed at speed mid
hours = sum(math.ceil(p / mid) for p in piles)
if hours <= h:
hi = mid # can finish, try slower
else:
lo = mid + 1 # too slow, need faster
return lo
# min_eating_speed([3,6,7,11], 8) => 4static int minEatingSpeed(int[] piles, int h) {
int lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int hours = 0;
for (int p : piles) hours += (p + mid - 1) / mid; // ceil
if (hours <= h) hi = mid;
else lo = mid + 1;
}
return lo;
}Time: O(n * log(max(piles))) — binary search over speeds, each check scans all piles. Space: O(1).
Capacity to Ship Packages
We need to ship packages in order within d days. Each day we load packages onto a ship with capacity cap. Find the minimum capacity (LeetCode #1011).
Same pattern. If capacity 10 works in d days, capacity 11 works too. Binary search on the capacity.
function shipWithinDays(weights, days) {
let lo = Math.max(...weights); // must fit the heaviest
let hi = weights.reduce((a, b) => a + b); // ship everything at once
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
// simulate: how many days needed with capacity mid?
let daysNeeded = 1, currentLoad = 0;
for (const w of weights) {
if (currentLoad + w > mid) {
daysNeeded++;
currentLoad = 0;
}
currentLoad += w;
}
if (daysNeeded <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}def ship_within_days(weights, days):
lo = max(weights) # must fit the heaviest
hi = sum(weights) # ship everything at once
while lo < hi:
mid = (lo + hi) // 2
# simulate: how many days with capacity mid?
days_needed, current_load = 1, 0
for w in weights:
if current_load + w > mid:
days_needed += 1
current_load = 0
current_load += w
if days_needed <= days:
hi = mid
else:
lo = mid + 1
return lostatic int shipWithinDays(int[] weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) { lo = Math.max(lo, w); hi += w; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int daysNeeded = 1, currentLoad = 0;
for (int w : weights) {
if (currentLoad + w > mid) {
daysNeeded++;
currentLoad = 0;
}
currentLoad += w;
}
if (daysNeeded <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}Time: O(n * log(sum(weights))), Space: O(1).
Split Array Largest Sum
Split an array into m subarrays to minimize the largest subarray sum (LeetCode #410). This one sounds like DP, but binary search on answer is cleaner.
The insight: we’re asking “what’s the minimum possible largest sum?” If the max sum is S and we can split into <= m parts, then S works. Binary search on S.
function splitArray(nums, m) {
let lo = Math.max(...nums);
let hi = nums.reduce((a, b) => a + b);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
// count splits needed if max sum per split is mid
let splits = 1, currSum = 0;
for (const n of nums) {
if (currSum + n > mid) {
splits++;
currSum = 0;
}
currSum += n;
}
if (splits <= m) hi = mid; // can do it, try smaller max
else lo = mid + 1; // too many splits, need larger max
}
return lo;
}
// splitArray([7,2,5,10,8], 2) => 18 ([7,2,5] and [10,8])def split_array(nums, m):
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = (lo + hi) // 2
splits, curr_sum = 1, 0
for n in nums:
if curr_sum + n > mid:
splits += 1
curr_sum = 0
curr_sum += n
if splits <= m:
hi = mid
else:
lo = mid + 1
return lo
# split_array([7,2,5,10,8], 2) => 18static int splitArray(int[] nums, int m) {
int lo = 0, hi = 0;
for (int n : nums) { lo = Math.max(lo, n); hi += n; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int splits = 1, currSum = 0;
for (int n : nums) {
if (currSum + n > mid) { splits++; currSum = 0; }
currSum += n;
}
if (splits <= m) hi = mid;
else lo = mid + 1;
}
return lo;
}Time: O(n * log(sum - max)), Space: O(1).
Notice how the last two problems (ship packages and split array) have essentially identical code? That’s the beauty of this pattern. Once we recognize it, the implementation almost writes itself.
Recipe for Binary Search on Answer
- Define the search space. What’s the minimum and maximum possible answer? (
loandhi) - Write the feasibility check. Given a candidate answer
mid, can we satisfy the constraints? This is usually a greedy simulation. - Binary search. If feasible, try smaller (for minimize) or larger (for maximize). If not feasible, go the other way.
In simple language, the hard part isn’t the binary search itself — that’s always the same. The hard part is recognizing that binary search on answer applies, and writing the feasibility check. Once we have those two pieces, the rest is mechanical.