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 findMinBruteForce(int[] nums) {
int min = nums[0];
for (int n : nums) {
min = Math.min(min, n);
}
return min;
}Time: O(n) · Space: O(1)