Find Minimum in Rotated Sorted Array II
Given a sorted array nums that was rotated and may contain duplicates, find the minimum element.
Intuition
In a rotated sorted array without duplicates, the minimum sits at the rotation point, and you find it by comparing nums[mid] to nums[right]: if mid is larger, the min must be in the right half; if smaller, the min is in the left half including mid. Duplicates ruin this when nums[mid] == nums[right] — you cannot tell which side holds the minimum. The remedy is to shrink right by one, since even if nums[right] is the minimum, nums[mid] holds the same value, so you haven't lost it. This shrink costs O(n) in the worst case but preserves correctness.
Finding the minimum in a rotated sorted array is a binary search for the 'drop point'. Without duplicates, comparing mid to right always resolves the direction. With duplicates, the tell is nums[mid] == nums[right] — you handle it by shrinking the window linearly. The pattern appears whenever a sorted-but-shifted structure has repeats.
Approach
Binary search comparing `nums[mid]` to `nums[right]`
Set left = 0, right = len(nums) - 1. Loop while left < right. Compute mid = (left + right) // 2. Compare nums[mid] with nums[right] to decide which half to keep.
When `nums[mid] > nums[right]`, the minimum is to the right
A value larger than the right end means the rotation point (where values drop) is somewhere between mid + 1 and right. Set left = mid + 1.
When `nums[mid] < nums[right]`, the minimum is to the left (including mid)
The right portion is already sorted and increasing, so the minimum cannot be after mid. Set right = mid — not mid - 1, because mid itself could be the minimum.
When `nums[mid] == nums[right]`, shrink `right` by one
You cannot distinguish the two halves. Decrement right — safe because if nums[right] was the minimum, nums[mid] is the same value and is still in the window. This is the only case duplicates add. When the loop ends, left == right and nums[left] is the minimum. Time is O(n) worst case, O(log n) average.
Solution
Common pitfalls
Comparing nums[mid] with nums[left] instead of nums[right]
if nums[mid] > nums[left]:
left = mid + 1if nums[mid] > nums[right]:
left = mid + 1Comparing with nums[left] does not reliably locate the minimum. For [3, 1, 2], nums[mid]=1 < nums[left]=3 suggests the min is on the left, but the min is mid. Comparing with nums[right] correctly distinguishes the sorted right half.
Setting right = mid - 1 when nums[mid] < nums[right]
right = mid - 1
right = mid
When nums[mid] < nums[right], mid itself could be the minimum (it is the smallest in the right portion). Skipping it with mid - 1 can jump past the answer. For [4, 5, 1, 2, 3] with mid at index 2, nums[2]=1 is the answer.
Using left <= right loop condition instead of left < right
while left <= right:
while left < right:
The algorithm converges left and right to the same index. With <=, when left == right, the loop runs one extra time, and mid == left == right, causing an infinite loop because none of the branches change left or right.
Edge cases
[3,3,3,3]The == branch fires every iteration, shrinking right one by one. Eventually left == right, and the answer is any element — all are the same.
nums[mid] <= nums[right] always holds, so right converges to left at index 0 — the smallest element.
[2, 1]mid = 0, nums[0] > nums[1], so left = 1. Loop ends, nums[1] = 1 is correct.