Find Minimum in Rotated Sorted Array

Difficulty: Medium

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.

Example

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.

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)