Search in Rotated Sorted Array
A sorted array of distinct integers was rotated at an unknown pivot, so it looks like two ascending runs. Given the rotated array and a target, return the index of the target or -1, in logarithmic time.
- 1 ≤ n ≤ 5000
- -10^4 ≤ nums[i], target ≤ 10^4
- All values distinct
- O(log n) required
- O(log n) demanded on an almost-sorted array
- At any midpoint, at least one half is properly sorted
- Decide which half is sorted, then whether the target lies in it
Sorted input, or any predicate that flips from false to true exactly once over an ordered range, means every comparison can discard half of the candidates. The "search space" need not be an array: it can be the answer itself (a speed, a capacity, a day) as long as feasibility is monotonic in that value.
Binary search on [lo, hi]. Compare nums[lo] with nums[mid] to determine which half is sorted. If the left half is sorted and the target lies within [nums[lo], nums[mid]), go left; otherwise go right. The mirror rule applies when the right half is sorted. One of the halves is always sorted, so the test is always decisive and the range halves each step.
- Find the rotation pivot with one binary search, then run a standard binary search on the correct run — two passes but simpler logic. A linear scan is O(n).