442. Search in Sorted Rotated Array (No Duplicates)

Given a sorted array of distinct integers that has been rotated at some pivot, and a target, return the index of target or -1 if not found. Solve in O(log n).

Input: A rotated sorted array of distinct integers and integer target.

Output: Index of target, or -1.

Examples

Input: [4,5,6,7,0,1,2], 0
Output: 4
Explanation: 0 is at index 4.

Input: [4,5,6,7,0,1,2], 3
Output: -1
Explanation: 3 not present.

Input: [1], 0
Output: -1
Explanation: Array has only 1; 0 not found.

Constraints

• 1 <= nums.length <= 5000
• All distinct
• -10^4 <= nums[i] <= 10^4

Asked by