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.
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
Worked example
- Suppose you need the smallest network bandwidth that can serve all requests.
- Define
P(b)= 'bandwidthbis 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 it
- 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.