core practice · coding problem
Search in a rotated sorted array
A sorted array was rotated at an unknown pivot. Find a target's index in O(log n).
The mechanism
Binary search is not about sorted arrays — it is about a monotonic predicate. If you can phrase the answer as "the smallest x for which condition(x) is true", you can binary-search the answer space, halving it each step.
Expected evidence
search([4,5,6,7,0,1,2], 0) -> 4
Try this drill in the practice workspace →
Hints when you need them
- At each step one half is still sorted — identify which.
- Decide whether the target lies in the sorted half, then recurse there.
Watch for these mistakes
- Infinite loops from a wrong mid update or loop condition
- Searching values when you should search the answer space
- Integer overflow in `(lo + hi) / 2` — use `lo + (hi - lo) / 2`