You are given an integer array nums with unique values. The array was originally sorted in ascending order and may have been rotated. If it was rotated, the rotation happened at an unknown pivot index x where 1 <= x < nums.length.
The resulting array is [nums[x], nums[x+1], ..., nums[n-1], nums[0], nums[1], ..., nums[x-1]] (0-indexed).

For example, the sorted array [0,1,2,3,5,6,7,9] could be rotated at index 4, resulting in [5,6,7,9,0,1,2,3].

Given the rotated array nums and an integer target, return the index of target if it exists in nums; otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,6,7,9,0,1,2,3], target = 6
Output: 1
Explanation: The array is rotated. Since 7 exists at index 1, return 1.

Example 2:

Input: nums = [4,6,7,0,1,2,3], target = 5
Output: -1
Explanation: The array is rotated. Since 5 does not exist, return -1.

Example 3:

Input: nums = [1,2,4,5,7,9], target = 7
Output: 4
Explanation: The array is not rotated. Since 7 exists at index 4, return 4.

Constraints

1 <= nums.length <= 5000

−10⁴ <= nums[i] <= 10⁴

All values of nums are distinct.

nums is an ascending array that is possibly rotated.

−10⁴ <= target <= 10⁴

61. Search in Rotated Sorted Array