Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums, return the minimum element.
Example 1
Input: nums = [3,4,5,1,2]
Output: 1
Example 2
Input: nums = [4,5,6,7,0,1,2]
Output: 0
n == nums.length1 <= n <= 5000All values of nums are unique.The minimum is at the inflection point. If mid > right, minimum is in the right half.
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1; // min is in right half
else right = mid; // mid might be the min
}
return nums[left];
}Time: O(log n) · Space: O(1)