Problem statement

A sorted ascending array of unique elements was rotated between 1 and n times. Given the rotated array nums, return its minimum element in O(log n) time.

Example 1

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

Example 2

Input: nums = [4,5,6,7,0,1,2]
Output: 0

Example 3

Input: nums = [11,13,15,17]
Output: 11
Explanation: Rotated 4 times — back to sorted.

Constraints

• 1 <= nums.length <= 30
• -100 <= nums[i] <= 100
• Unique values.

Hints for Find Minimum in Rotated Sorted Array

1. Hint 1

   Compare nums[mid] with nums[hi]: if greater, the minimum is to the right of mid.

2. Hint 2

   Shrink toward the unsorted side until lo == hi.

How to solve Find Minimum in Rotated Sorted Array

The minimum is the single point where the array "drops" — the start of the second sorted run. Comparing nums[mid] against the last element of the current range tells you which side of that drop you are on, so you can halve the range without ever seeing the whole array.

Approach

1. Keep a range [lo, hi] and loop while lo < hi.
2. Take mid = lo + (hi - lo) / 2.
3. If nums[mid] > nums[hi], the drop is strictly after mid — set lo = mid + 1.
4. Otherwise mid could itself be the minimum — set hi = mid.
5. When the range collapses, nums[lo] is the minimum.

Why it works

Comparing against nums[hi] rather than nums[lo] is what makes this clean. If nums[mid] > nums[hi] then mid sits in the first (higher) run while hi sits in the second, so the wrap-around point lies to the right and mid cannot be the answer. Otherwise mid is already in the run containing the minimum, and the minimum is at mid or before it — so keeping mid in range is required. The invariant "the minimum is in [lo, hi]" holds throughout, and the range strictly shrinks, so lo lands on it. A non-rotated array simply always takes the second branch.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Compare with nums[hi], not nums[lo]. The lo version needs extra cases to handle an unrotated array.
• Use hi = mid, not mid - 1 — mid may be the minimum itself.
• The loop condition is lo < hi; with <= and hi = mid it never terminates.
• Return the value at lo, not the index.

Reference solution

Python

from typing import List

def findMin(nums: List[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Java

public static int findMin(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
}

C++

int findMin(vector<int>& nums) {
    int lo = 0, hi = (int) nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
}

JavaScript

var findMin = function(nums) {
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium