dsa · medium
Search in Rotated Sorted Array
nums is a distinct-valued array that was sorted ascending, then rotated at an unknown pivot (possibly 0). Return the index of target, or -1 if it is absent. The search must be logarithmic in n.
Arguments
nums— distinct values, originally sorted, then rotatedtarget— value whose index to return, or -1
Example
nums = [4,5,6,7,0,1,2], target = 0 → 4.
nums = [4,5,6,7,0,1,2], target = 3 → -1.
[1], 0 → -1.
Constraints
1 <= nums.length <= 5000 All values in nums are unique -10^4 <= nums[i], target <= 10^4 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [4,5,6,7,0,1,2] 0 Expected: 4
Example 2
Input: [4,5,6,7,0,1,2] 3 Expected: -1
Example 3
Input: [1] 0 Expected: -1