Search in Rotated Sorted Array
MediumBinary search
nums was sorted in ascending order with no repeated values, then rotated: some values from the front were moved to the back, keeping their order. [1, 3, 5, 7, 9] could now be [7, 9, 1, 3, 5].
Given nums and a target, return the index of target in nums, or -1 if it is not there. Aim for O(log n) time.
Examples
Input: nums = [7, 9, 1, 3, 5], target = 3 Output: 3
3 is at index 3.
Input: nums = [7, 9, 1, 3, 5], target = 4 Output: -1
4 is not in the array.
Constraints
1 ≤ nums.length ≤ 5000-10⁴ ≤ nums[i], target ≤ 10⁴- All values in
numsare different.
Stuck?
Hint 1
Cut the array in the middle. At least one of the two halves is still sorted, and comparing its ends tells you which.
Hint 2
If the target is inside the sorted half’s range, search there; otherwise search the other half.
The idea
Cut a rotated array in the middle and at least one of the two halves is still in order. Comparing the ends of a half tells you which, and a half that is in order can say for certain whether target falls inside it. So every step still throws away half the range, as in an ordinary binary search.
Time O(log n)Extra space O(1)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
Search the range from low to high, both ends included, so the loop runs while the range holds at least one value. >> 1 halves the sum and drops any fraction.
function search(nums, target) { let low = 0; let high = nums.length - 1; while (low <= high) { const mid = (low + high) >> 1; if (nums[mid] === target) return mid; if (nums[low] <= nums[mid]) { if (nums[low] <= target && target < nums[mid]) high = mid - 1; else low = mid + 1; } else { if (nums[mid] < target && target <= nums[high]) low = mid + 1; else high = mid - 1; } } return -1;}The trap
An ordinary binary search assumes the whole array is sorted and goes right whenever the middle value is smaller than target. That works when nothing was rotated, or when target happens to lie on the side the comparison points to. When the middle is on one side of the drop and target is on the other, the half holding target is thrown away and the search answers -1.
function search(nums, target) { let lo = 0, hi = nums.length - 1; // plain binary search: assumes no rotation while (lo <= hi) { const mid = (lo + hi) >> 1; if (nums[mid] === target) return mid; if (nums[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1;}