38. Search in Rotated Sorted Array
MediumBinary search
A sorted array of distinct integers was rotated at an unknown pivot (for example [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]). Return the index of target, or -1. Aim for O(log n).
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
Constraints
1 ≤ nums.length ≤ 5000All values are distinct