visual walkthrough
Search in Rotated Sorted Array
Decide which half is sorted; one of the most-asked Mediums.
The idea
Turning a sorted array breaks it at one point, so when you cut it in the middle, at least one half has no break and is sorted.
You can test whether the target lies inside a sorted range with two comparisons. If it does, go there; if not, it's in the other half.
Complexity
| approach | time | space |
|---|---|---|
| Scan everything | O(n) | O(1) |
| Binary search with a sorted half | O(log n) | O(1) |