Find Minimum in Rotated Sorted Array
Problem
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
nums = [4,5,6,7,0,1,2]0def 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];
}Explanation
The array was sorted and then rotated, so it has one "drop" where the smallest value sits. The neat idea is that you can still binary-search for that drop, even though the array is not fully sorted, by comparing the middle value against the right end.
If nums[mid] > nums[hi], the right half is "out of order," which means the minimum must be somewhere after mid, so we move lo = mid + 1. Otherwise the right half is tidy and the minimum is at mid or to its left, so we set hi = mid (keeping mid as a candidate).
The window keeps halving until lo == hi, and that single surviving index points at the minimum, which we return as nums[lo].
Example: nums = [4,5,6,7,0,1,2]. At first mid = 7 and nums[hi] = 2, so 7 > 2 pushes us right past the big values. The window collapses on index 4, giving the answer 0.
Because every step throws away half the remaining elements, this runs in O(log n) time with O(1) extra space.