Find a Value in an Array Rotated at an Unknown Pivot
Implement searchRotated
An array, sorted in ascending order with all-distinct values, is 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 its index, or -1 if it isn't present.
You must solve it in O(log n) time. At every step, at least one of the two halves around mid is guaranteed to be sorted — use that half to decide which side to search next.
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
+ 4 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 5000 - ●
-10⁴ ≤ nums[i] ≤ 10⁴ - ●
Every value in nums is unique - ●
nums was sorted in ascending order, then rotated at some unknown pivot - ●
-10⁴ ≤ target ≤ 10⁴
nums =
[4, 5, 6, 7, 0, 1, 2]
target =
0