Find the Target in a Rotated Sorted Array

You are given an integer array nums, sorted in ascending order with distinct values, that has been rotated at an unknown pivot (for example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Given nums and an integer target, return the index of target in nums, or -1 if it is not present.

Your algorithm must run in O(log n) time.

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

Constraints

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values in nums are unique.
• nums is an ascending array possibly rotated at some pivot.
• -10^4 <= target <= 10^4