Binary search and monotone answer · HTML
For minimization, design can(x) as F…F T…T and find first True; for maximization, design T…T F…F and find last True.
Recognition signals
- The objective minimizes a maximum or maximizes a minimum.
- Checking a proposed threshold is clearly easier than constructing the optimum.
- Candidate answers live in a bounded integer or discrete domain.
- More time, capacity, or resources cannot invalidate an already feasible plan.
False friends
| Signal | Why it is different |
|---|
| Nonmonotone feasibility | If increasing x can switch success back to failure, binary search is invalid. |
| Huge domain with an expensive predicate | Applicability does not imply speed; a direct greedy, heap, or selection method may dominate. |
Core invariant
The closed interval [lo,hi] contains the optimum boundary; for first True, values left of lo are excluded and hi remains a feasible candidate.
State, transition, and processing order
| Item | Definition |
|---|
| State | Semantic lower bound lo, feasible upper bound hi, midpoint, and a can(mid) function answering only feasibility. |
| Transition | If can(mid) is true, retain mid with hi=mid; otherwise set lo=mid+1. |
| Frontier / order | The unresolved answer-value domain, halved only after a complete feasibility decision. |
Python skeleton
def minimize_feasible(lo, hi, can):
# Precondition: the optimum is in [lo, hi] and can(hi) is True.
while lo < hi:
mid = lo + (hi - lo) // 2
if can(mid):
hi = mid
else:
lo = mid + 1
return lo
Correctness sketch
- If mid is feasible, the minimum feasible value is at most mid, so retain the left half including mid.
- If mid is infeasible, monotonicity makes every smaller value infeasible as well, so exclude them together.
- The interval converges to a feasible value with no smaller feasible predecessor, exactly the optimum boundary.
Complexity
| Time | Space | Parameters |
|---|
| O(C log W) | O(S) | W=hi-lo+1 is answer-domain width; one feasibility check costs time C and space S. |
Edge cases
- Derive lo and hi from semantics, not arbitrary constants.
- If can(hi) is not guaranteed, expand the upper bound or detect no solution.
- When only input-derived values matter, binary-search the sorted unique candidate list.
- In fixed-width languages compute mid as lo+(hi-lo)//2.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Solving the full optimum inside can | The predicate should answer only whether the threshold suffices, remaining simple enough to prove monotone. |
| Searching in the wrong direction | Write the False/True picture before choosing which side feasibility retains. |
| Forgetting the log factor | A cost-C predicate executes logarithmically many times. |
Selection and exclusion rules
- First ask: if I guess x, can I verify it in O(C)?
- Then prove that increasing x changes feasibility in only one direction.
- Compare C log W with a direct algorithm; binary search is not automatically faster.
Original micro-example
| Part | Detail |
|---|
| Result | The first feasible capacity, 7, is the minimum answer. |
| Setup | Work must finish within D days; guess daily capacity x and greedily check completion. |
| Trace | Every capacity below 7 fails and every capacity at least 7 succeeds; binary search calls only can(x). |
Recall prompts
My notes