nums started as an array of distinct integers in ascending order. Then it was rotated: some of the elements (possibly none) were moved from the front to the back, keeping their order. For example, [2, 4, 6, 8, 10] can become [8, 10, 2, 4, 6].
Return the index of target in nums, or -1 if it is not there. The search has to run in O(log n) time.
Example 1
Input
nums = [15, 18, 22, 3, 6, 9, 12], target = 6
Output
4
Explanation
the sorted array [3, 6, 9, 12, 15, 18, 22] had its first four values moved to the back. 6 is now at index 4.
Example 2
Input
nums = [15, 18, 22, 3, 6, 9, 12], target = 10
Output
-1
Explanation
no element of the array equals 10.
Constraints:
1 <= nums.length <= 5000
all values in nums are distinct
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.