Find Minimum in Rotated Sorted Array

Signal

"Sorted, but rotated" is still binary search — one of the two halves around any midpoint is always properly sorted, and that fact alone is enough to steer the search toward the rotation point without ever scanning linearly.

Approach

Compare nums[mid] against nums[right]. If nums[mid] > nums[right], the minimum (the rotation point) must be somewhere to the right of mid, so move left past it. Otherwise the right half (including mid) is already sorted and contains the minimum, so pull right down to mid. Converge until left == right.

Skeleton

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]

Solution

def find_min(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]

Complexity

O(log n) time — halves the search window each step. O(1) space.

Pitfalls

• Comparing nums[mid] to nums[left] instead of nums[right] is the classic mistake — it doesn't reliably tell you which side is sorted when mid equals left. Anchor on right.
• Using right = mid - 1 after finding a sorted right half would skip past the minimum if mid itself is the minimum — use right = mid, keeping it in the window.
• If the array isn't guaranteed distinct (duplicates allowed), nums[mid] == nums[right] becomes ambiguous and you can only shrink the window by one (right -= 1) instead of halving it — worth flagging that the follow-up degrades to O(n) worst case.