Search in Rotated Sorted Array
MediumBinary Search · Amazon · Google · NVIDIA
An array of unique integers was sorted in ascending order and then possibly rotated at an unknown pivot: the elements from some index onward were moved, in order, to the front. For example, [0, 1, 2, 4, 6, 7] rotated so that it starts at 6 becomes [6, 7, 0, 1, 2, 4]. The array may also not be rotated at all.
Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it is not present.
Your solution must run in O(log n) time.
Example 1
- Input:
- nums = [6,7,0,1,2,4], target = 2
- Output:
- 4
- Explanation
- The array drops from 7 to 0, so it is two ascending runs:
[6, 7]and[0, 1, 2, 4]. 2 is in the second run, at index 4.
Example 2
- Input:
- nums = [30,40,50,10,20], target = 40
- Output:
- 1
- Explanation
- Here the drop is from 50 to 10, and 40 is in the first run
[30, 40, 50], at index 1.
Example 3
- Input:
- nums = [6,7,0,1,2,4], target = 3
- Output:
- -1
- Explanation
- 3 would belong between 2 and 4 in the second run, but it is not there, so the answer is -1.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i], target <= 10^4- All values in
numsare unique numsis an ascending array that may have been rotated