Search in Rotated Sorted Array
Problem
A sorted array of distinct integers has been rotated at some unknown pivot, so it looks like two ascending runs glued together. Given a target, return its index or -1 if it is not present. Your search must run in O(log n).
Examples
Constraints
- • 1 <= nums.length <= 5000
- • All values are distinct
- • nums is an ascending array rotated some number of times
Hints & approach
Hint 1
Pick any mid. At least one of the two halves around it is still fully sorted.
Hint 2
Compare nums[lo] with nums[mid] to find out which half is sorted.
Hint 3
If the target lies inside the sorted half's range, search there; otherwise search the other half.
Approachtry the hints first
Run a normal binary search, but at each step decide which side of mid is sorted. If nums[lo] <= nums[mid], the left half is sorted: when nums[lo] <= target < nums[mid] move hi to mid - 1, else move lo to mid + 1. Otherwise the right half is sorted: when nums[mid] < target <= nums[hi] move lo to mid + 1, else move hi to mid - 1. Each step still discards half the range, so the search stays logarithmic.
Time O(log n) · Space O(1)