77. Search in Rotated Sorted Array

An integer array was sorted in ascending order then rotated at an unknown pivot. Given nums and target, return the index of target or -1. Must run in O(log n) time.

Input: A rotated sorted array nums (distinct values) 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 found.

Input: [1],0
Output: -1
Explanation: 0 not in [1].

Constraints

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

Asked by