Find Minimum in Rotated Sorted Array

Difficulty: Medium

Problem

Take a sorted array of distinct values in ascending order and rotate it by some amount from 1 to n positions (n is its length), so a tail chunk moves to the front. You are given the resulting array nums. Return its smallest element, with an algorithm that runs in O(log n) time. The array has at least one element (1 <= n).

Example

Input: nums = [6, 7, 9, 1, 3, 4]
Output: 1
Explanation: The original array was [1, 3, 4, 6, 7, 9], rotated so that 6, 7, 9 moved to the front.

Brute-force approach

Scan through the entire array to find the minimum element.

Steps

  1. Initialize min as the first element
  2. Iterate through the array
  3. Update min whenever a smaller element is found

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • O(n) doesn't meet the O(log n) requirement
  • Doesn't take advantage of the sorted/rotated structure

Optimal approach

Key insight: If nums[mid] > nums[right], the rotation point is in the right half. Otherwise, it's in the left half (including mid).

Binary search: compare mid with right to determine which half contains the minimum (rotation point).

Steps

  1. Initialize left=0, right=n-1
  2. While left < right, compute mid
  3. If nums[mid] > nums[right] → minimum is in [mid+1, right]
  4. Else → minimum is in [left, mid]
  5. When left == right, that's the minimum

Time complexity: O(log n) · Space complexity: O(1)

Pseudocode

function findMin(nums):
    if len(nums) == 0: return None    // guard (n >= 1 by the statement)
    left = 0
    right = len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    
    return nums[left]

Hints

  • The minimum is the first cell after the drop (the one cell smaller than its predecessor), or the first cell when there is no drop (nothing moved)
  • Compare nums[mid] with nums[right] to determine which half contains the minimum
  • If nums[mid] > nums[right], the minimum must be in the right half

Check your understanding of Find Minimum in Rotated Sorted Array

Why do we compare nums[mid] with nums[right] instead of nums[left]?

Comparing with nums[right] correctly identifies which half has the rotation point. When nums[mid] > nums[right], the rotation point (minimum) must be in [mid+1, right]. When nums[mid] <= nums[right], the right half is sorted and the minimum is in [left, mid]. Comparing with nums[left] doesn't work for all cases: [1, 3, 4, 6, 7, 9] and [6, 7, 9, 1, 3, 4] both have nums[mid] > nums[left] at the first mid, but the first needs the minimum on the left (nothing moved) and the second needs the right half, so the same test asks for opposite moves.

Why do we use 'while left < right' instead of 'while left <= right'?

Because we're not looking for a specific target: we're shrinking the window to a single element. We're not searching for a target value. We're narrowing down the search space until left == right, which points to the minimum. Using left <= right could cause an infinite loop since we set right = mid (not mid-1).

Related problems

Keep practising