Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array.
- n == nums.length, 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All integers in nums are unique
nums = [3,4,5,1,2]1nums = [4,5,6,7,0,1,2]0A rotated sorted array is a strange landscape: it's not one single mountain, but two separate ascending slopes separated by a "Cliff."
The most obvious way is to scan the array from left to right. You look for the moment a number becomes smaller than the one before it. That drop-off point is your minimum.
- The Cost: If the minimum is at the very end of a 10,000-element array, you've done 10,000 checks. This is O(N) efficiency.
Because we have two sorted slopes, any guess in the middle tells us exactly where the "Cliff" (the minimum) is hiding.
Discovery: Compare your Midpoint to the Right Boundary.
1. If Mid > Right: You are standing on the "High Slope." The cliff must be somewhere to your right. You can safely discard the entire high ground you are standing on.
2. If Mid < Right: You are standing on the "Low Slope." The absolute minimum is either exactly where you are, or somewhere to your left. You can discard everything further down the slope to your right.
left = 0
right = length - 1
WHILE left < right:
mid = left + (right - left) / 2
// Compare mid to the absolute right boundary
IF nums[mid] > nums[right]:
// We are on the high slope, jump to the right
left = mid + 1
ELSE:
// We are on the low slope, the min is at or left of mid
right = mid
RETURN nums[left]Binary Search is the perfect tool for "Rotated" problems because it allows us to identify which segment of the array we are in using just one comparison. We don't need to find the "pivot" point first; by comparing against the boundaries, we let the search window naturally collapse around the cliff-drop until only the minimum remains.
Finding the Pivot Point
The minimum element is the only one that is smaller than its previous element. We find this "cliff" by comparing Mid against Right.