153. Find Minimum in Rotated Sorted Array

← All Problems
medium Binary Search
Given a sorted array of unique integers that has been rotated between 1 and n times, find the minimum element. For example, [3,4,5,1,2] is [1,2,3,4,5] rotated 3 times, and the minimum is 1. The array has length n and contains values in the range [-5000, 5000]. Your algorithm must run in O(log n) time.

Example

nums = [3, 4, 5, 1, 2]

Output: 1

The original sorted array [1, 2, 3, 4, 5] was rotated 3 times to produce [3, 4, 5, 1, 2]. The minimum element is still 1.

Use binary search comparing the middle element to the rightmost element. If mid is greater than right, the minimum must be in the right half (the rotation point is there). Otherwise the minimum is in the left half including mid. This narrows the search by half each step.

Why this works

In a rotated sorted array, the minimum is at the “rotation point” where the values drop. Comparing nums[mid] to nums[right] tells you which side the drop is on. If mid is larger than right, the drop (and minimum) must be somewhere to the right. Otherwise, the minimum is at mid or to its left.

Step by step

  1. Compare mid to right — if nums[mid] > nums[right], the array is still “broken” between mid and right, so the minimum is in that right portion.
  2. Narrow the window — set left = mid + 1 (mid is too large to be the min) or right = mid (mid itself could be the min).
  3. Converge — repeat until left == right. That single element is the minimum.
Time: O(log n) Space: O(1) 
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {  // rotation point is to the right of mid
                left = mid + 1;
            } else {  // mid could be the minimum, so keep it in range
                right = mid;
            }
        }
        return nums[left];  // left == right, both point to the minimum
    }
}

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {  // rotation point is to the right of mid
                left = mid + 1;
            } else {  // mid could be the minimum, so keep it in range
                right = mid;
            }
        }
        return nums[left];  // left == right, both point to the minimum
    }
};

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:  # rotation point is to the right of mid
            left = mid + 1
        else:  # mid could be the minimum, so keep it in range
            right = mid
    return nums[left]  # left == right, both point to the minimum