Find Minimum In Rotated Sorted Array

When the array is rotated, the minimum sits at the one place where an element is smaller than the element before it (the rotation point); in the fully sorted case it is simply nums[0]. Scanning for that dip works, but it never uses the fact that both halves of the array are individually sorted, which is what makes O(log n) possible.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        minimum = nums[0]
        for num in nums:
            minimum = min(minimum, num)
        return minimum

Compare nums[mid] to nums[hi] (the current right endpoint), not to nums[lo]. If nums[mid] > nums[hi], the rotation point — and therefore the minimum — must lie strictly to the right of mid, because a sorted run cannot have a larger value in the middle than at its own end. Otherwise, nums[mid] <= nums[hi] means the right half from mid to hi is already sorted and internally contains the minimum of that half, so the minimum is at mid or to its left, and it is safe to keep mid in play by setting hi = mid.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        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]

Watch how each comparison to the right endpoint decides which half, and how many indices, can be thrown away.

Why it’s correct: the array is made of at most two sorted runs; comparing nums[mid] to nums[hi] always determines which run mid belongs to and thus which side the minimum is on, without ever discarding it. Complexity: the search window halves each iteration, giving O(log n) time, O(1) space.