Find Minimum in Rotated Sorted Array

Find the smallest value in a sorted array that was rotated once.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Find Minimum in Rotated Sorted Array: Retain the minimum by comparing middle with the current right boundary.

Input and goalFind the smallest value in a sorted array that was rotated once.

Keep middle and everything leftleft=0, right=7, middle=3. Since nums[3]=1 <= nums[7]=5, middle may be the minimum; set right=middle=3.

left607182middle13243546right57

interval[0, 7]comparison1 <= 5decisionright = 3

Recognize it

Distinct values form two increasing runs after one rotation, and the task asks for the smallest value rather than a particular target.

Keep true

The minimum is always inside inclusive [left, right]. If nums[middle] exceeds nums[right], middle is on the high run; otherwise middle may be the minimum and must be retained.

Reuse it

Pivot searches depend on choosing an endpoint reference and preserving the candidate when equality or ordering does not prove it impossible; this same boundary discipline applies to first-occurrence searches.

Pattern: Binary search against the right value.

Simple idea: If the middle value is larger than the right value, the minimum must be to the right of the middle. Otherwise, the middle may be the minimum, so keep it.

def find_min_rotated(nums: list[int]) -> int:
   left, right = 0, len(nums) - 1

   while left < right:
      middle = (left + right) // 2
      if nums[middle] > nums[right]:
         left = middle + 1
      else:
         right = middle
   return nums[left]

Cost: $O(\log n)$ time and $O(1)$ space.