Rotated Array Search

You are given an integer array nums of distinct values that was originally sorted in ascending order, then possibly left-rotated at an unknown pivot index k (0 <= k < nums.length), turning it into [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. For example, the ascending array [0,1,2,4,5,6,7] rotated at pivot 3 becomes [4,5,6,7,0,1,2].

You are also given an integer target. Return the index of target in nums after the possible rotation, or -1 if it is not present.

You must write an algorithm that runs in $O(\log n)$ time.

Examples

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: nums[4] == 0, so the answer is index 4.

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: 3 does not occur in nums.

Example 3

Input: nums = [1], target = 0
Output: -1