Search in Rotated Sorted Array

Medium

Given a rotated ascending array of distinct integers nums and a target, return its index or -1. Must run in O(log n).

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
• All values distinct.
• nums is a rotation of an ascending array.