Find Minimum in Rotated Sorted Array II
Problem
Given a sorted array that has been rotated and may contain duplicates, return the minimum value.
nums = [2, 2, 2, 0, 1]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
elif nums[mid] < nums[hi]:
hi = mid
else:
hi -= 1
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 if (nums[mid] < nums[hi]) hi = mid;
else hi--;
}
return nums[lo];
}class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else if (nums[mid] < nums[hi]) hi = mid;
else hi--;
}
return nums[lo];
}
}int findMin(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else if (nums[mid] < nums[hi]) hi = mid;
else hi--;
}
return nums[lo];
}Explanation
This is a rotated sorted array — sorted, then "cut" and moved — and the minimum sits at the cut point. We find it with binary search, comparing the middle value against the right end instead of the left.
If nums[mid] > nums[hi], the cut must be to the right of mid, so we set lo = mid + 1. If nums[mid] < nums[hi], then mid could be the minimum or it lies to the left, so hi = mid (we keep mid in the window).
The twist in this version is duplicates. When nums[mid] == nums[hi] we cannot tell which side holds the minimum, so we safely shrink with hi -= 1. We lose one element but never the true minimum, since an equal copy still remains at mid.
Example: nums = [2,2,2,0,1]. With mid on a 2 and nums[hi] = 1, 2 > 1 sends us right. The window narrows onto the 0, and we return nums[lo] = 0.
Usually this is O(log n), but a run of equal values (the hi -= 1 case) can degrade it to O(n) in the worst case.