Search in Rotated Sorted Array

A sorted array of distinct integers was rotated at an unknown point (possibly not at all), e.g. [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2].

Given the rotated nums and a target, return the index of target, or -1 if it's missing. Your solution 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

Example 3

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

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i], target <= 10^5
• All values are distinct.