Module 13 · Binary Search
Practice
Practice~1 min
How to practice this module
Binary-search drills reward the invariant: name what the search region guarantees, then shrink it. Insert position and first/last are boundary searches; rotated-array tests the pivot split; Koko and minimum-rotated are binary search on the answer. Done when all five show Solved in the hub.
Problems
Binary Search — work them in order; difficulty ascends.
0/5
solved
- 1Search Insert PositionEasyLower-bound searchWatch for: The invariant decides the answer — return lo, not lo-1 or hi; a single-element array is the edge case
- 2Find First and Last PositionMediumTwo boundary searchesWatch for: First and last are separate lower/upper-bound walks; an absent target must return [-1, -1]
- 3Search in Rotated Sorted ArrayMediumPivot-aware binary searchWatch for: Detect which half is sorted and check membership there — the rotation breaks the naive mid comparison
- 4Koko Eating BananasMediumBinary search on the answerWatch for: Speed is monotonic in time; search the range [1, max(pile)] and the feasibility check must run in O(n)
- 5Find Minimum in Rotated Sorted ArrayMediumPivot minimumWatch for: Compare mid with the right end to decide which side holds the minimum — the pivot is the drop between sorted halves
Cheatsheet
Binary Search — Halve a monotonic search space — on arrays or on the answer.
Smell → pattern
- Sorted array lookup / boundClassic binary search
- Min feasible capacity / days / speedSearch on answer
- First true / last false in a predicateLower / upper bound
- Peak / bitonic arrayCompare mid to neighbours
- Rotated sorted arrayIdentify the sorted half
Patterns
Classic midpoint
CoreSmell: Find a target in a sorted array
Maintain [lo, hi] where the answer may live. Mid = lo + (hi − lo) // 2 — avoids overflow. Shrink the half that cannot contain the target.
Search on answer
SafeSmell: Minimise / maximise a numeric capacity
When feasibility is monotonic in a numeric answer, binary search that number and run a linear check. The check — not the mid formula — is the hard part.
Lower / upper bound
ReachSmell: First index where predicate becomes true
Loop until lo == hi; return that boundary. Decide inclusive/exclusive carefully — ‘first true’ and ‘last false’ differ by one.
Rotated / bitonic half
CarefulSmell: Sorted array that was rotated, or a peak
Compare mid to an endpoint (or neighbour) to learn which half is sorted / ascending. Search the half that still can hold the answer.
Complexity targets
Array binary search
- Time
- O(log n)
- Space
- O(1)
- Note
- Sorted input
Answer search + check
- Time
- O(check · log R)
- Space
- O(1)
- Note
- R = answer range
Rotated search
- Time
- O(log n)
- Space
- O(1)
- Note
- One sorted half each step
| Move | Time | Space | Note |
|---|---|---|---|
| Array binary search | O(log n) | O(1) | Sorted input |
| Answer search + check | O(check · log R) | O(1) | R = answer range |
| Rotated search | O(log n) | O(1) | One sorted half each step |
Traps
Infinite loop on bounds
Ensure every branch moves lo or hi. Using mid and mid±1 inconsistently with an inclusive range is the usual hang — write the invariant first.
Non-monotonic check
Search-on-answer only works when ‘feasible(x)’ never flips back. If the predicate wiggles, binary search returns nonsense — prove monotonicity first.