Binary Search on the Answer
Sometimes you’re not searching an array at all — you’re searching a range of possible answers, and binary search still applies.
The problem
A cargo ship must carry a line of packages across the ocean, in order, in D days. Each
day it loads packages onto the belt up to the ship's weight capacity, then sails. Bigger
capacity means fewer days but a pricier ship. You want the smallest capacity that still
delivers everything within D days.
Notice there's no array of answers to look through. The thing you're searching for — the capacity — is a number in a range. It could be as small as the heaviest single package (you must be able to carry it) or as large as the sum of all weights (carry everything in one day). Somewhere in that range is the smallest capacity that works.
A first attempt
Just try every capacity, smallest first. Start at max(weights), simulate the voyage, and
if it takes more than D days, bump the capacity by one and try again. The first capacity
that fits is your answer.
It's correct, but the range of capacities can be enormous — up to the total weight, which
might be millions. Each trial re-simulates all n packages. That's O(range × n), far too
slow when the range is huge.
The insight
Ask a yes/no question instead of a value question: "Can we deliver in D days with capacity
C?" Write a helper feasible(C) that simulates the voyage and returns true or false.
Now look at how feasible behaves as C grows:
capacity: 5 6 7 8 9 10 11 12
feasible: N N N F T T T T
└── the boundary we wantIt's monotonic — once a capacity works, every larger capacity also works. A sorted line
of falses followed by trues is exactly what binary search eats. We binary-search the
capacity range for the leftmost C where feasible(C) flips to true. That's binary
search on the answer.
The tell
Any time a problem says "minimize the maximum" or "maximize the minimum" or "smallest X that
still works", check for monotonic feasibility. If feasible(x) being true implies
feasible(x+1) is true, you can binary-search x — even though nothing is stored in a
sorted array.
How it works
Bound the answer range
The smallest sensible capacity is max(weights) (you must carry the heaviest package). The
largest is sum(weights) (everything in one day). The answer lives in [lo, hi].
Write the feasibility check
feasible(C): sweep the packages, greedily filling each day until adding the next would
exceed C, then start a new day. Count the days; return days <= D.
Binary-search the range
Take mid = lo + (hi - lo) / 2. If feasible(mid), this capacity works but a smaller one
might too — keep it and search left (hi = mid). Otherwise search right (lo = mid + 1).
Return the boundary
When lo == hi, that's the smallest feasible capacity. Because feasible is monotonic, it's
guaranteed to be a true value.
The code
def min_capacity(weights, days):
def feasible(cap):
d, load = 1, 0
for w in weights:
if load + w > cap:
d += 1
load = 0
load += w
return d <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lofunction minCapacity(weights: number[], days: number): number {
const feasible = (cap: number): boolean => {
let d = 1;
let load = 0;
for (const w of weights) {
if (load + w > cap) {
d += 1;
load = 0;
}
load += w;
}
return d <= days;
};
let lo = Math.max(...weights);
let hi = weights.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (feasible(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}boolean feasible(int[] weights, int cap, int days) {
int d = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
d++;
load = 0;
}
load += w;
}
return d <= days;
}
int minCapacity(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;
if (feasible(weights, mid, days)) hi = mid;
else lo = mid + 1;
}
return lo;
}#include <stdbool.h>
bool feasible(const int weights[], int n, int cap, int days) {
int d = 1, load = 0;
for (int i = 0; i < n; i++) {
if (load + weights[i] > cap) {
d++;
load = 0;
}
load += weights[i];
}
return d <= days;
}
int min_capacity(const int weights[], int n, int days) {
int lo = 0, hi = 0;
for (int i = 0; i < n; i++) {
if (weights[i] > lo) lo = weights[i];
hi += weights[i];
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(weights, n, mid, days)) hi = mid;
else lo = mid + 1;
}
return lo;
}bool feasible(const std::vector<int>& weights, int cap, int days) {
int d = 1, load = 0;
for (int w : weights) {
if (load + w > cap) {
d++;
load = 0;
}
load += w;
}
return d <= days;
}
int minCapacity(const std::vector<int>& weights, int days) {
int lo = 0, hi = 0;
for (int w : weights) {
lo = std::max(lo, w);
hi += w;
}
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(weights, mid, days)) hi = mid;
else lo = mid + 1;
}
return lo;
}Complexity
| Aspect | Cost | Why |
|---|---|---|
| Time | O(n · log(range)) | log(range) binary-search steps, each an O(n) check |
| Space | O(1) | the greedy check uses a couple of counters |
Here range = sum(weights) − max(weights). Compare that to the naive O(range · n) — the
log turns millions of trials into ~20.
When to use it
The check must be monotonic — verify it
Binary search on the answer is only valid when feasible never flips back: true must stay
true as the parameter moves toward the "easier" end. If feasibility can turn true, then false,
then true again, the search can land on the wrong boundary. Also mind the direction — for
"maximize the minimum" the true/false pattern is reversed, so you keep the right half on
success. This pattern powers Koko eating bananas, splitting an array to minimize the largest
sum, the smallest divisor, and aggressive-cows spacing.
Practice
Recap
- When the unknown is a number in a range and "does value
xwork?" is monotonic, you can binary-search the answer — no array required. - Write a boolean
feasible(x), bound the range, and find the boundary where false flips to true; keep the half that could hold a better answer. - Cost is
O(n · log(range))— thelogcollapses a huge search space, but only if the feasibility check is genuinely monotonic.
How is this guide?
Last updated on