Find Minimum in Rotated Sorted Array II
Find the minimum in a rotated sorted array that may contain duplicates — binary search with shrink-on-tie.
3 min read
binary-search
Problem#
Rotated sorted array with possible duplicates. Return the minimum.
Examples#
[2,2,2,0,1]→0[1,3,5]→1
Constraints#
1 <= n <= 5000.
Approach#
Binary search comparing nums[mid] to nums[hi]. If less, minimum is in [lo..mid]; if greater, in (mid..hi]; equal — can’t tell, shrink --hi.
Solution#
class Solution {public: int findMin(vector<int>& nums) { int lo = 0, hi = nums.size() - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (nums[mid] < nums[hi]) hi = mid; else if (nums[mid] > nums[hi]) lo = mid + 1; else --hi; } return nums[lo]; }};func findMin(nums []int) int { lo, hi := 0, len(nums)-1 for lo < hi { mid := lo + (hi-lo)/2 if nums[mid] < nums[hi] { hi = mid } else if nums[mid] > nums[hi] { lo = mid + 1 } else { hi-- } } return nums[lo]}from typing import List
class Solution: def findMin(self, nums: List[int]) -> int: lo, hi = 0, len(nums) - 1 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] < nums[hi]: hi = mid elif nums[mid] > nums[hi]: lo = mid + 1 else: hi -= 1 return nums[lo]function findMin(nums) { let lo = 0, hi = nums.length - 1; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (nums[mid] < nums[hi]) hi = mid; else if (nums[mid] > nums[hi]) lo = mid + 1; 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]) hi = mid; else if (nums[mid] > nums[hi]) lo = mid + 1; else hi--; } return nums[lo]; }}function findMin(nums: number[]): number { let lo = 0, hi = nums.length - 1; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); if (nums[mid] < nums[hi]) hi = mid; else if (nums[mid] > nums[hi]) lo = mid + 1; else hi--; } return nums[lo];}Editorial#
Compare to hi (not lo!) — lo-comparison is ambiguous for the “no rotation” case. Equal values at mid and hi mean the minimum could still be at hi, so we can safely shrink one. The “ascending suffix” half always contains the minimum.
Complexity#
- Time: O(log n) typical, O(n) all-duplicate worst case.
- Space: O(1).
Concept revision#
Related#