When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Sorted values
- Monotonic feasibility
When another approach fits better
- The predicate can switch true/false more than once
- The domain is tiny or an ordinary linear scan is clearer within constraints
How it works#
Scan the ordered values or every candidate answer until the first feasible one is found.
Choose closed or half-open bounds and say what they contain.
Define the predicate and prove monotonicity.
Use the midpoint outcome to preserve the answer-containing interval; return the boundary named by the invariant.
InvariantThe answer remains inside the declared interval, and each update strictly shrinks that interval.
Example and template#
First Bad Version
Makes a monotonic predicate and boundary contract explicit.
Open the full problem brief- Candidates
F F F T T TSearch for the first true boundary.
- Mid is true
F F F [T] T TKeep mid because it may be the first true; discard everything to its right.
left = first_candidate
right = one_past_last_candidate
while left < right:
mid = left + (right - left) // 2
if feasible(mid): right = mid
else: left = mid + 1
return left- Time
- O(log m) predicate evaluations
- Space
- O(1) extra
- Assumptions
- m is finite ordered domain size and feasibility is monotonic.
Pitfalls#
Common wrong approaches
Using a half-open loop with closed-interval updates can stall or skip the boundary.
A sorted-looking input is not enough when the chosen predicate oscillates.
Edge cases
- Empty domain
- Answer at either boundary
- No feasible candidate
- Midpoint overflow in fixed-width languages
Interview narration
- “I am searching for the first candidate where this predicate becomes true.”
- “The interval is half-open, so right itself is excluded.”
- “A true midpoint remains possible; a false midpoint and everything before it are impossible.”
Practice#
First Bad Version
Makes a monotonic predicate and boundary contract explicit.
Practice this problemFind the minimum server capacity that completes all jobs before a deadline.
Reveal the pattern decision
Binary-search capacity only after proving that any larger capacity remains feasible.
Transfer problem
Return the insertion boundary for a value in a sorted array containing duplicates.
Checkpoint: Define whether you need first ≥ target or first > target and dry-run both ends.
Follow-up variations
- Search a rotated sorted array by identifying the ordered half
- Search real-valued answers with an explicit precision/iteration contract
Error-log prompts
- What exactly was inside my interval?
- Where did I prove monotonicity?