94. Search in Rotated Sorted Array

Medium · Binary Search

You are given a rotated sorted array of unique integers and a target value. A rotated sorted array is created by taking a sorted array and rotating it some number of times (possibly zero). For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] after rotating 4 times. Find the index of the target in the array, or return -1 if it is not present.

You must solve this problem in O(log n) time complexity.

Examples

Example 1
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: The target 0 is found at index 4 in the rotated array.
Example 2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: The target 3 does not exist in the array, so return -1.

Constraints