Look for monotonicity
Values, positions, or possible answers split into two regions: too small / large enough, false / true, infeasible / feasible.
Coding Patterns/04 · Monotonic decisions
Binary search is a proof of elimination.
Keep the answer inside
Before every iteration, the answer—if one exists—must remain inside the active interval. Every boundary move needs a proof.
Decide whether mid survives
Use mid ± 1 only after proving mid cannot be the answer. Use right = mid when mid is still a valid candidate.
Runnable session
Code the boundary.
Five exercises · Python 3 · visible checks · saved locally
Easy18 min target
Release Lookup
Implement find_release(releases, target). releases is a sorted list of unique integer build numbers. Return the index of target, or -1 when it is absent.
Examples
Input releases = [101, 108, 115, 121, 144], target = 121
Output 3
Build 121 is at zero-based index 3.
Input releases = [101, 108, 115], target = 110
Output -1
110 falls between two builds but is not present.
Constraints
- 0 ≤ len(releases) ≤ 100,000
- Build numbers are strictly increasing
- Return an index, not the build number
Your code runs privately in the browser. Visible checks cover empty, boundary, and representative cases.
Worked referenceTrace: find 31 in seven values+
The interval only keeps possible answers.
The closed interval starts at [0, 6]. Each comparison preserves the invariant and removes a proven-impossible region.
19 is too small. Indices 0 through 3 cannot contain 31.
42 is too large. Indices 5 and 6 cannot contain 31.
The final remaining candidate matches the target.
A linear scan could need five; the gap grows rapidly with input size.