Problem Statement
Minimum in Rotated Sorted Array II
You have a list of numbers that was sorted from small to large, then someone "rotated" it. Rotating means they took a chunk from the front and moved it to the back. So [0,1,2,4,5,6,7] could become [4,5,6,7,0,1,2]. Your job is to find the smallest number in it. The tricky part of this version is that the list can have repeats (duplicates), like [2,2,2,0,1]. Repeats matter because they can hide the clue we use to pick a side. We will look at the middle number and compare it to the rightmost number. When those two are equal, we honestly cannot tell which side holds the smallest, so we shrink the search by stepping the right edge in by one. That is safe, because even if the right number was the minimum, the middle has the exact same value, so we did not lose it. For every other case, normal binary search works.
Signals to notice
Brute force first
Linear scan — O(n).
The key insight
Binary search: compare mid with right. If mid > right, min is right of mid. If mid < right, min is left of/at mid. If equal, shrink right by 1. Average O(log n), worst O(n).
Trace it on nums=[2,2,2,0,1]
init: left=0, right=4 mid=2, nums[2]=2 > nums[4]=1 -> min is right of mid, left=3 mid=3, nums[3]=0 < nums[4]=1 -> min at/left of mid, right=3 left==right==3 -> loop exits return nums[3] = 0
What must stay true
When nums[mid] == nums[right], you can't determine which half has the minimum — safe to shrink right by 1 since the equal value still exists at mid.
Shape of the loop
left, right = 0, n-1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]: left = mid + 1
elif nums[mid] < nums[right]: right = mid
else: right -= 1 # duplicate: shrink safely
return nums[left]Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Shrinking left instead of right — right is safer because if right equals mid, the value is preserved at mid.