Find Minimum in Rotated Sorted Array

How it works

In a rotated sorted array, the minimum element is the first element of the rotated portion.
Using binary search, we compare the middle value with the rightmost value:

• If nums[mid] < nums[right], then the minimum lies in the left half (including mid).
• Otherwise, the minimum lies in the right half (excluding mid).

This behaves exactly like finding a lower bound, gradually shrinking the search space until only the minimum remains.

Steps

1. Set left = 0 and right = n - 1.
2. While left < right:
   • Compute mid.
   • If nums[mid] is less than nums[right], move right to mid (minimum is on the left).
   • Otherwise, move left to mid + 1 (minimum is on the right).
3. When the loop ends, left points to the smallest element.
4. Return nums[left].

Complexity

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

Things to watch for

Comparing Mid with Left Instead of Right

In the lower bound approach, comparing nums[mid] with nums[left] instead of nums[right] can lead to incorrect boundary updates, especially when the array is not rotated or rotated by n positions. Comparing with the rightmost element consistently determines which half contains the minimum.

Off-by-One Errors in Boundary Updates

When nums[mid] < nums[right], the minimum could be at mid itself, so set right = mid (not mid - 1). When nums[mid] >= nums[right], the minimum must be in the right half, so set left = mid + 1. Using wrong update logic either skips the minimum or causes infinite loops.

Not Handling the Non-Rotated Case

A sorted array with no rotation (or rotated by n positions) is still valid input. The minimum is simply the first element. Some binary search implementations fail on this edge case by not recognizing that the entire array is already sorted. Always check if nums[left] < nums[right] to detect this case early.

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            m = l + (r - l) // 2
            if nums[m] < nums[r]:
                r = m
            else:
                l = m + 1
        return nums[l]

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] < nums[r]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
};