Given a rotated sorted array of unique elements, find the minimum element in O(log n) time.
Example 1
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The array was rotated so 1 (the original minimum) sits at index 3.
Example 2
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: 0 is the minimum.
1 <= nums.length <= 5000All values are uniqueThe minimum element is exactly the 'pivot point' where the rotation happened — everything before it is >= the first element, everything from it onward is < the first element.
Compare nums[mid] against nums[right], not nums[left] — it gives a cleaner signal for which side the minimum is on.
If nums[mid] > nums[right], the minimum must be to the right of mid (the rotation point hasn't been passed yet); otherwise it's at or before mid.
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1; // minimum is to the right — mid is still on the 'high' side of the rotation
} else {
right = mid; // minimum is at mid or to its left — don't exclude mid itself
}
}
return nums[left]; // left == right at the loop's end, pointing at the minimum
}Time: O(log n) · Space: O(1)