Find Minimum in Rotated Sorted Array

A sorted array was rotated, e.g. [3, 4, 5, 1, 2]. Compare the middle with the rightmost element: if nums[mid] > nums[hi], the drop (and the minimum) is to the right of mid; otherwise the minimum is at mid or to its left.

Traced input: nums = [4, 5, 6, 7, 0, 1, 2] → 0. Original problem: neetcode.io/problems/find-minimum-in-rotated-sorted-array

Complexity

Values are distinct, so every comparison discards half.

Key idea

• The minimum is the only element smaller than its predecessor: the rotation point.
• nums[mid] > nums[hi] means the rotation point is in (mid, hi].
• Otherwise [mid, hi] is sorted, so the minimum is in [lo, mid].
• Stop when lo == hi.

Common mistakes

• Comparing with nums[lo] instead of nums[hi] breaks on arrays that aren't rotated.
• Using hi = mid - 1 in the else branch can skip the minimum.

Solution

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];
}

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]

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];
}

Edge cases

Each one has its own trace in the interactive view.