Search in Rotated Sorted Array

You get an integer target and an array nums of different integers.

Return the index of target in nums, or -1 if nums doesn't have it.

The numbers in nums were sorted from smallest to largest. Then the array may have been rotated. A rotation moves the first k numbers to the end, in the same order. Here 0 <= k < nums.Length.

For example, [2,5,8,10,13] with k = 2 becomes [8,10,13,2,5]. With k = 0, nothing moves.

Example 1:

Input: nums = [15,18,22,3,7,11], target = 7
Output: 4
Explanation: The sorted array was rotated with k = 3.
So 3, 7 and 11 moved to the end.
7 is at index 4.

Example 2:

Input: nums = [9,12,2,5], target = 6
Output: -1
Explanation: 6 is not in the array.

Example 3:

Input: nums = [8], target = 8
Output: 0

Constraints:

• 1 to 1,000,000 numbers.
• All numbers are different.
• target and each number are from -10⁹ to 10⁹.
• The array is sorted, then maybe rotated (see above).