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.

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):
    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 element is the only element smaller than its predecessor (the rotation point)
  • 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.

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