141. Find Minimum in Rotated Sorted Array II

Like the no-duplicates version, compare mid with hi. When they're equal, we can't decide which half, so shrink hi by 1. This degrades to O(n) worst case but handles duplicates.

Approach

Binary search, but with one twist for duplicates.

1. Set lo = 0, hi = n - 1.
2. While lo < hi:
   • Compute mid = (lo + hi) // 2.
   • If nums[mid] > nums[hi]: the minimum must be to the right of mid (the rotation pivot is in the right half). Set lo = mid + 1.
   • If nums[mid] < nums[hi]: mid could be the minimum, or it's to the left. Set hi = mid.
   • If nums[mid] == nums[hi]: we can't tell which half the minimum is in. Safely shrink the window by doing hi -= 1 (if nums[hi] was the minimum, nums[mid] has the same value, so we won't lose it).
3. Return nums[lo].

Walk-through

Input: nums = [2, 2, 2, 0, 1, 2]

Why it works

In a rotated sorted array without duplicates, comparing nums[mid] to nums[hi] always tells you which half contains the pivot. Duplicates break this when nums[mid] == nums[hi] because both halves look identical. Shrinking hi by 1 is safe: if nums[hi] is the minimum, nums[mid] holds the same value and stays in the search window.

Edge cases

• No rotation ([1,2,3]): nums[mid] < nums[hi] every step, converges to index 0.
• All duplicates ([2,2,2,2]): keeps doing hi -= 1, degrades to O(n) but still returns the correct value.

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else if (nums[mid] < nums[hi]) {
                hi = mid;
            } else {
                hi--;
            }
        }
        return nums[lo];
    }
}