Algorithms / Answer Space Binary Search
Least You Need to Know: Binary Search on Answers and Monotone Predicates
Sometimes you do not binary-search an array index at all. Instead you binary-search an **answer space** such as a capacity, time limit, or threshold, using a feasibility check that flips from false to true exactly once.
The least you need to know
- Binary search on answers needs a monotone yes/no predicate over candidate answers.
- A feasibility check answers whether a candidate value is sufficient, not what the exact optimal construction is.
- This pattern is common when the prompt asks for the smallest capacity, minimum speed, or minimum maximum load that works.
- If the predicate is not monotone, binary search can discard the wrong side.
- The answer interval shrinks based on whether the current candidate is feasible.
Key notation
P(x)
feasibility predicate for candidate answer x
false...false true...true
monotone transition needed for first-true search
search space
candidate answer values, not positions in an array
Tiny worked example
- Suppose you need the smallest network bandwidth that can serve all requests.
- Define `P(b)` = 'bandwidth `b` is enough'.
- If `P(mid)` is true, keep smaller candidates by moving the right boundary left.
- If `P(mid)` is false, larger candidates are still needed, so move the left boundary right.
Common mistakes
- Students often binary-search an optimization problem before checking whether feasibility becomes monotone.
- Students often confuse the checker's job with constructing the final schedule or arrangement.
- Students often choose a search range that does not actually contain the optimal answer.
How to recognize this kind of problem
- The prompt says smallest feasible, minimum capacity, or minimum speed.
- You can write a yes/no checker for any fixed candidate answer.
- Larger candidates never turn a feasible instance back into an infeasible one.
Next recommended lesson
Continue through this topic with Least You Need to Know: Big-O, Theta, and Omega.
Least You Need to Know: Big-O, Theta, and OmegaRelated lessons
Keep going with nearby lessons in the same topic.