Search in Rotated Sorted Array
Medium Find the sorted half
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A sorted array of distinct values was rotated at an unknown point. Find target's index in O(log n), or -1.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: binary search in a sorted array that was rotated.
Why this works: at any mid, one half is still properly sorted. Check if the target lies in that half's range; otherwise search the other half.
Example: [4, 5, 6, 7, 0, 1, 2], target 0
mid 3 (7): left half 4..7 sorted, 0 not in it → go rightmid 5 (1): left half 0..1 sorted, 0 in it → go leftmid 4 (0) ✓
✦Hints open one at a time
↗Approach
If nums[lo] <= nums[mid], the left half is sorted: go left when nums[lo] <= target < nums[mid]. Otherwise the right half is sorted: go right when nums[mid] < target <= nums[hi].
</>Solution (Java)
class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
}!Common mistake
Using < instead of <= in nums[lo] <= nums[mid]; when lo == mid the left "half" is one element and is sorted.
- Time: O(log n).
- Space: O(1).