Find Minimum in Rotated Sorted Array

Problem Statement

A sorted array of unique values is rotated at an unknown pivot. Return the minimum element in O(log n).

Example

Input:  nums = [3,4,5,1,2]
Output: 1

Approach

Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum must be to the right of mid, so set left = mid + 1. Otherwise the minimum is at mid or to its left, so set right = mid. The loop ends at the minimum.

Complexity

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

Solution Code

Python

def findMin(nums):
    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]

Java

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

C++

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

Key Takeaways

• Compare with the right end, not the left, to find the pivot cleanly.
• No equality branch is needed because the values are unique.
• Reference: LeetCode 153 (Find Minimum in Rotated Sorted Array).