Minimum in Rotated Sorted Array II
hardTime: O(log n)Space: O(1)
Signals to notice
minimum in rotated sorted array with duplicatesworst case O(n)ambiguous mid comparison
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).
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.
Easy way to go wrong
Shrinking left instead of right — right is safer because if right equals mid, the value is preserved at mid.