Find Minimum in Rotated Sorted Array — Binary Search

Find Minimum in Rotated Sorted Array is the gateway problem to a whole family of “broken sorted array” puzzles. The key insight is that even after rotation, one half of the array is still sorted, and that half tells you where the pivot is not.

The Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, [0,1,2,4,5,6,7] rotated four times becomes [4,5,6,7,0,1,2].

Given this rotated array nums of unique elements, return the minimum element. The minimum is the rotation pivot.

You must write an algorithm that runs in O(log n) time.

Intuition

After rotation, the array consists of two sorted runs. The minimum element is the first element of the second run. Comparing nums[mid] with nums[right] is unambiguous:

• If nums[mid] > nums[right], the left half ascends past nums[right], so the pivot must lie in (mid, right] — set left = mid + 1.
• Otherwise, the pivot is at mid or to its left — set right = mid.

Comparing against nums[right] (not nums[left]) is what handles the non-rotated case correctly, because for any already-sorted array nums[mid] <= nums[right] always holds and the loop quietly converges to index 0.

Explanation with Example

Walking through nums = [4,5,6,7,0,1,2]:

• left = 0, right = 6, mid = 3. nums[3] = 7, nums[6] = 2. Since 7 is greater than 2, left = 4.
• left = 4, right = 6, mid = 5. nums[5] = 1, nums[6] = 2. Since 1 is not greater than 2, right = 5.
• left = 4, right = 5, mid = 4. nums[4] = 0, nums[5] = 1. Since 0 is not greater than 1, right = 4.
• Loop exits. Return nums[4] = 0.

Three comparisons for a length-seven array, matching the O(log n) bound.

step  left  right  mid  nums[mid]  vs nums[right]   action
1    0     6      3       7        7 > 2           left = mid+1 = 4
2    4     6      5       1        1 < 2           right = mid  = 5
3    4     5      4       0        0 < 2           right = mid  = 4
4    4     4      --      --       loop ends       return nums[4] = 0

Code

Note the asymmetric update: left = mid + 1 but right = mid. The + 1 on the left is safe because we have proved the minimum lies strictly past mid. We cannot use it on the right because the minimum might be exactly mid.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]

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]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

#include <vector>
using namespace std;

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

What About Duplicates?

If duplicates are allowed, the comparison nums[mid] > nums[right] no longer gives you a definitive direction when the two values are equal. The standard fix is to shrink the search space by one on equality: right -= 1. This makes the worst case O(n) but only triggers on degenerate inputs like [2, 2, 2, 2, 2].

Edge Cases

A few inputs are worth tracing through:

• Already sorted (zero rotations). The minimum is nums[0].
• Single element. The loop never runs; we return nums[0].
• Two elements. One iteration decides which is smaller.
• Rotation by n (full rotation, equivalent to zero rotations). Same as already sorted.

The algorithm handles all of these without any special-case branches.

Complexity Analysis

Time complexity is O(log n). Each iteration halves the search range.

Space complexity is O(1). Two integer pointers regardless of input size.

Extending the Pattern

Once you have this in your toolkit, you can attack:

• Search in Rotated Sorted Array, where you adapt the same invariant to look for a target.
• The duplicates variant of this problem.
• Peak Index in a Mountain Array, where the comparison flips because you are looking for the peak.

The unifying idea is “compare midpoint to a fixed end, decide which half is the sorted run, throw it away.”

Wrapping Up

Find Minimum in Rotated Sorted Array trains a mental move that pays off across many binary-search variants: pick a comparison that is unambiguous at every state of the array, then halve the search space accordingly. Burn the nums[mid] > nums[right] invariant into memory and the related problems will feel familiar.