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.
บทเรียนถัดไปที่แนะนำ
เรียนต่อในหัวข้อนี้ด้วย Least You Need to Know: Big-O, Theta, and Omega
Least You Need to Know: Big-O, Theta, and Omegaบทเรียนที่เกี่ยวข้อง
เรียนต่อด้วยบทเรียนใกล้เคียงในหัวข้อเดียวกัน