Find Minimum in Rotated Sorted Array

The machine must return the minimum of a rotated sorted array with distinct values. The insight: the minimum is the pivot point where the order breaks. Compare the midpoint against the high element: if nums[mid] > nums[hi], the pivot is in the right half; otherwise the right half is continuous, so the pivot lies in the left half including mid.

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Steps: (1) narrow the window to the side that contains the break, (2) when lo == hi, that slot holds the minimum.

Time is O(log n). Space is O(1).

Trickiest edge case: an unrotated array like [11,13,15,17]. The minimum is at index 0; the comparison nums[mid] > nums[hi] is never true, so hi creeps left toward 0 — the loop ends at lo == hi == 0. The inclusive hi = mid (not mid - 1) is what keeps the minimum inside the window; dropping it loses the answer when mid itself is the minimum.