154. Find Minimum in Rotated Sorted Array II

Intuition

In a rotated sorted array, the minimum lies in the unsorted side. With duplicates, comparisons can become ambiguous, so when nums[mid] == nums[r], we cannot decide a side and safely shrink r by one. Otherwise, comparing nums[mid] with nums[r] still tells which half contains the minimum.

Algorithm

1Set l = 0, r = n - 1.
2While l < r, compute mid = l + (r - l) / 2.
3If nums[mid] < nums[r], minimum is in [l..mid], so set r = mid.
4If nums[mid] > nums[r], minimum is in [mid+1..r], so set l = mid + 1.
5If nums[mid] == nums[r], decrement r by 1 to remove ambiguity.
6When loop ends, l points to the minimum value; return nums[l].

Example Walkthrough

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

1.l=0, r=4, mid=2 → nums[mid]=2, nums[r]=1, so nums[mid] > nums[r] → l=3.
2.l=3, r=4, mid=3 → nums[mid]=0, nums[r]=1, so nums[mid] < nums[r] → r=3.
3.l==r==3, stop. nums[3]=0 is minimum.

Output: 0

Common Pitfalls

•With duplicates, worst-case becomes O(n) because repeated nums[mid] == nums[r] may shrink one step at a time.
•Using while (l <= r) can be tricky for this pattern; while (l < r) avoids out-of-range returns and simplifies termination.
•Always compare against nums[r] in this variant; mixing comparison targets inconsistently can break correctness.

154.cs

// Approach: Binary search on rotated array with duplicates.
// Compare mid with right boundary: if nums[mid] < nums[r], min is in [l..mid];
// if nums[mid] > nums[r], min is in [mid+1..r]; if equal, shrink r by one.
// Time: O(log n) average, O(n) worst case (many duplicates) Space: O(1)

public class Solution
{
    public int FindMin(int[] nums)
    {
        int n = nums.Length;
        int l = 0, r = n - 1, mid = 0;

        while (l <= r)
        {
            mid = (l + r) / 2;
            if (nums[r] == nums[mid])
            {
                r--;
                continue;
            }
            else if (nums[r] > nums[mid])
                r = mid;
            else
                l = mid + 1;
        }

        return nums[l];
    }
}

Was this solution helpful?