Find Minimum in Rotated Sorted Array
Given a sorted array that has been rotated at some unknown pivot, find the minimum element. The array contains unique elements and the solution must run in O(log n). **Core Insight:** Binary search on the rotation. The minimum element is at the "inflection point" — where the array transitions from a large value back to a small one. At any midpoint: if `nums[mid] > nums[right]`, the minimum is in the right half (the rotation is in the right half). Otherwise the minimum is in the left half (including mid itself). **Algorithm:** Set `left = 0`, `right = n - 1`. While `left < right`: compute `mid`. If `nums[mid] > nums[right]` set `left = mid + 1`. Else set `right = mid`. Return `nums[left]`. **Why compare with right (not left):** Comparing with `nums[right]` cleanly identifies which half is "out of order" and therefore contains the minimum. **Complexity:** Time O(log n) — the window halves each step. Space O(1).
Constraints
- •
n == nums.length - •
1 ≤ n ≤ 5000 - •
All integers are unique
def findMin(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]