Minimum in a Rotated Sorted Array
Problem
An array of distinct values was originally sorted ascending and then rotated. Return the smallest value.
Input
nums = [4,5,6,7,0,1,2]Output
0Compare nums[mid] with nums[hi]: if nums[mid] > nums[hi], the pivot lies to the right of mid; otherwise it is at or before mid.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}
}int findMin(vector<int>& nums) {
int lo = 0, hi = (int) nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}