103. Search in Rotated Sorted Array
Problem
You are given an integer array nums sorted in ascending order with distinct values. Before being passed to your function, nums may have been rotated at an unknown pivot. Given nums and target, return the index of target if it exists. Otherwise, return -1. Your solution should run in O(log n) time.
Examples
Example 1
Input: [4,5,6,7,0,1,2], 0
Output: 4
The target 0 is located at index 4.
Example 2
Input: [4,5,6,7,0,1,2], 3
Output: -1
The target 3 does not exist in the array.
Example 3
Input: [1], 0
Output: -1
The only element is 1, so target 0 is absent.
Constraints
� 1 <= nums.length <= 5000
� -10^4 <= nums[i] <= 10^4
� All values of nums are unique.
� nums is an ascending array that may have been rotated.
� -10^4 <= target <= 10^4
Hints
?? At least one half of the current search range must always be sorted.
?? Determine whether the left or right half is sorted before deciding where the target may exist.
?? Discard one half on every iteration to maintain O(log n) time.
Expected Complexity
Follow-up
Can you solve the problem using O(log n) time and O(1) extra space?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
[4,5,6,7,0,1,2], 0Expected
4