An array of distinct integers, sorted in ascending order, has been rotated at some unknown pivot. For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].
Given the rotated array nums and an integer target, return the index of target, or -1 if it isn't in nums. Aim for O(log n) time.
Examples
Example 1
- Input
- nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- Output
- 4
Example 2
- Input
- nums = [4, 5, 6, 7, 0, 1, 2], target = 3
- Output
- -1
Example 3
- Input
- nums = [1], target = 0
- Output
- -1
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i], target <= 10^4- All values in
numsare distinct.