Binary search, including on the answer
Halve a search space whose predicate flips once from false to true, whether the space is an array or a range of possible answers.
Capacity To Ship Packages Within D Days. Packages weights must ship in order. Each day the ship carries a contiguous run whose total is at most its capacity. Return the smallest capacity that ships everything within days days.
Signals that point here
- Sorted input and a target, or "first / last position where...".
- "Minimise the maximum" or "maximise the minimum".
- A yes/no check
fits(x)that is monotone: once true, true for every largerx. - Constraints like
n ≤ 10⁵and values up to10⁹, which rule out trying every answer.
The idea
Do not search the array; search the answer. Capacity c either works or not, and if c works so does c + 1. That monotone predicate is all binary search needs.
Use one template and never improvise: lo < hi, mid = (lo + hi) // 2, hi = mid when the predicate holds, lo = mid + 1 when it fails. It returns the first value where the predicate is true, and it cannot loop forever.
def ship_within_days(weights: list[int], days: int) -> int:
def fits(cap: int) -> bool:
need, load = 1, 0
for w in weights:
if load + w > cap:
need, load = need + 1, 0
load += w
return need <= days
lo, hi = max(weights), sum(weights)
while lo < hi: # first capacity where fits() is True
mid = (lo + hi) // 2
if fits(mid):
hi = mid
else:
lo = mid + 1
return lopublic static class BinarySearch
{
public static int ShipWithinDays(int[] weights, int days)
{
bool Fits(int cap)
{
int need = 1, load = 0;
foreach (int w in weights)
{
if (load + w > cap) { need++; load = 0; }
load += w;
}
return need <= days;
}
int lo = weights.Max(), hi = weights.Sum();
while (lo < hi) // first capacity where Fits() is true
{
int mid = lo + (hi - lo) / 2; // no overflow
if (Fits(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
}Complexity
O(n log S) where S is the sum of weights: log S probes, each a linear fits check. O(1) extra space.
Pitfalls interviewers watch for
lo <= hiwithhi = mid: an infinite loop whenlo == hi.- Wrong bounds: starting
loat 1 instead ofmax(weights)makesfitswrong, not just slow. (lo + hi) / 2overflowing in C# or Java when values near2³¹; writelo + (hi - lo) / 2.- A predicate that is not monotone. Say why it is before you rely on it.
Variants worth knowing
- Classic lower bound on a sorted array: predicate
a[mid] >= target. - Search in a rotated sorted array: decide which half is sorted, then which half holds the target.
- Koko eating bananas, split array largest sum, minimum days to make bouquets: same template, different
fits.
Test it like the interviewer will
ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)returns15ship_within_days([3, 2, 2, 4, 1, 4], 3)returns6ship_within_days([1, 2, 3, 1, 1], 4)returns3ship_within_days([10], 1)returns10- Say the cases out loud before you run them. OpenAI's published guide names test coverage as part of the bar; see Sources.
Step through it: ship_within_days([3, 2, 2, 4, 1, 4], 3)
Each step is recorded from an instrumented copy of the Python above, run when the site was built.
Practice
Written for this site to drill the lesson. Not reported interview questions.
- Return the first and last index of
targetin a sorted array. - Find the minimum eating speed that finishes all piles within
hhours. - Find the minimum in a rotated sorted array with no duplicates.
Check yourself
What property must the predicate have?
Monotone: false for every value below the answer, true for every value at or above it.
What does the lo < hi, hi = mid template return?
The first value for which the predicate is true.