Intermediate · Module 9 · Lesson 5
Binary search on answer
Find the first feasible or last valid candidate.
Lesson 51 of 123
1d streakBinary Search on Answer Space: Feasibility Predicates
When optimizing a metric (e.g. minimum eating speed, maximum allocation capacity), if checking whether a candidate answer X is feasible forms a monotonic predicate f(X) -> {false, false, ..., true, true}, binary search can pinpoint the optimal answer in O(log(range) * cost(check)).
public int minEatingSpeed(int[] piles, int h) {
int low = 1, high = Arrays.stream(piles).max().getAsInt();
while (low < high) {
int mid = low + (high - low) / 2;
if (canFinish(piles, mid, h)) {
high = mid; // Feasible; try smaller speed
} else {
low = mid + 1; // Infeasible; speed must increase
}
}
return low;
}
private boolean canFinish(int[] piles, int speed, int h) {
long hours = 0;
for (int p : piles) hours += (p + speed - 1) / speed;
return hours <= h;
}Active Recall Checkpoint
Why is (p + speed - 1) / speed used instead of Math.ceil((double) p / speed)?
Show answer & explanation
Integer arithmetic avoids double floating-point precision inaccuracies on large integers while performing exact ceiling division.
Use it when
Use binary search on answer space for minimax/maximin optimization problems: allocating books, ship capacity, aggressive cows, and split array largest sum.
Reconsider when
Reconsider when the feasibility predicate is non-monotonic (e.g. where validity fluctuates unpredictably between true and false).
Cost Model
Complexity & Trade-offs
When to use it
- Exact lookup, first/last occurrence, rotated order, and answer-space optimization.
- Any monotonic yes/no feasibility boundary.
- Implicit ordered spaces where values need not be materialized.
Common mistakes
- Mixing inclusive and half-open interval updates.
- Using binary search without proving monotonicity.
- Returning the last middle value instead of the stored boundary.
Practice prompts
- Reproduce the worked Binary search on answer example without looking at the trace.
- Change one input condition and explain whether the Binary search on answer invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check