Search in Rotated Sorted Array
Problem
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.
Examples
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.
Constraints
- •
1 <= nums.length <= 5000 - •
All values are unique - •
nums is an ascending array rotated at some pivot
Hints
Hint 1
A 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.
Hint 2
Once you know which half is sorted, checking whether the target lies within that half's range is an O(1) comparison.
Hint 3
If the target isn't in the sorted half's range, it must be in the other (unsorted-looking, but still binary-searchable) half.
Solutions
public int searchBruteForce(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) return i;
}
return -1;
}Time: O(n) · Space: O(1)