Search in Rotated Sorted Array
Medium · binary search
A list of distinct integers was sorted in ascending order and then rotated: some number of items were moved from the front to the back, keeping their order. For example, [0, 1, 2, 4, 5, 6, 7] rotated by 4 positions becomes [5, 6, 7, 0, 1, 2, 4]. You are not told how far it was rotated.
Given the rotated list nums and an integer target, return the index of target in nums, or -1 if it is not there.
Examples
Example 1
Input: nums = [5, 6, 7, 0, 1, 2, 4], target = 1
Output: 4
nums[4] is 1.
Example 2
Input: nums = [5, 6, 7, 0, 1, 2, 4], target = 3
Output: -1
3 is not in the list.
Example 3
Input: nums = [8], target = 8
Output: 0
Constraints
- 1 <= len(nums) <= 5000
- -10^4 <= nums[i], target <= 10^4
- All values in nums are distinct.
- nums is an ascending list rotated by some number of positions (possibly 0).