Given a sorted array nums that has been rotated at an unknown pivot, and a target value, return the index of target if it exists, otherwise -1, in O(log n) time.
Example 1
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: 0 is at index 4.
Example 2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: 3 is not in the array.
1 <= nums.length <= 5000All values are uniquenums is an ascending array rotated at some pivotA rotated sorted array isn't fully sorted, but at every midpoint, at least ONE of the two halves IS fully sorted — that's the property to exploit.
Once you know which half is sorted, checking whether the target lies within that half's range is an O(1) comparison.
If the target isn't in the sorted half's range, it must be in the other (unsorted-looking, but still binary-searchable) half.
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // left half is sorted
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}Time: O(log n) · Space: O(1)