loading

Find Minimum in Rotated Sorted Array — Step-by-Step Visualization

mediumLeetCode #153ArrayBinary Search

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.

Algorithm Pattern

Binary Search on Rotated Range

Key Idea

Since the array was originally sorted, the rotation creates two sorted halves. The minimum element is the only element that is smaller than its predecessor, and it's also the element we are looking for using binary search. If `nums[mid] >= nums[left]`, it means the left half is sorted, so the minimum must be in the right half. Otherwise, it's in the left half.

Step-by-Step Approach

  1. Initialize `left = 0`, `right = len(nums) - 1`, and `res = nums[0]`.
  2. Check mid: `mid = (left + right) // 2`.
  3. Update `res = min(res, nums[mid])`.
  4. If `nums[mid] >= nums[left]`: the left portion is sorted. If `nums[mid] > nums[right]`, the minimum must be to the right, so `left = mid + 1`. Otherwise, search left.
  5. Wait, simpler: if `nums[mid] >= nums[left]`, search right if `nums[mid] > nums[right]`. Else search left.
  6. Actually, the standard approach is: if `nums[mid] >= nums[l]`, we check if it's the 'big' part. If `nums[mid] > nums[r]`, it's definitely in the right half.

Common Gotchas

  • The array might not be rotated at all (0 rotations), in which case `nums[0]` is the min.
  • Always update the result with `nums[mid]` at every step.

Related Problems

← All problems