Minimum in Rotated Sorted Array II
hardTime: O(log n)Space: O(1)
Recognize the pattern
minimum in rotated sorted array with duplicatesworst case O(n)ambiguous mid comparison
Brute force idea
Linear scan — O(n).
Better approach
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).
Key invariant
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.
Watch out for
Shrinking left instead of right — right is safer because if right equals mid, the value is preserved at mid.