LeetEye LeetEye
Medium Binary Search ~5 min

Find Minimum in Rotated Sorted Array

binary-search find-minimum-in-rotated-sorted-array

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

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

Examples

Example 1
Input: nums = [3,4,5,1,2]
Output: 1
Example 2
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Example 3
Input: nums = [11,13,15,17]
Output: 11
Array not rotated (or rotated n times), minimum at start.
Key Insight

The minimum is where the "break" happens — where a larger element is followed by a smaller one.

Compare mid with right: if mid > right, minimum is in right half (left = mid + 1). Else minimum is at mid or left (right = mid). Converge to find break point.

How to Approach This Problem

Pattern Recognition: When you see keywords like find minimum in rotated sorted array binary-search, think Binary Search.

Step-by-Step Reasoning

1 In a rotated sorted array, the minimum element is:
Answer: At the rotation point (where the "break" occurs)
[4,5,6,7,0,1,2] — minimum 0 is where the sequence breaks from 7 to 0.
2 If the array is sorted (not rotated or rotated n times), minimum is at:
Answer: Index 0
[1,2,3,4,5] — standard sorted, minimum is first element.
3 We compare nums[mid] with nums[right] because:
Answer: It tells us which half contains the minimum
If mid > right, the break is between mid and right (min is right of mid). If mid < right, this portion is sorted, so min is at or left of mid.
4 If nums[mid] > nums[right], the minimum is:
Answer: To the right of mid
Mid being greater than right means there's a "drop" somewhere between mid and right. The minimum is in the right half.
5 If nums[mid] < nums[right], the minimum:
Answer: Might be at mid itself
The portion from mid to right is sorted. The minimum could be mid or something to its left. Don't exclude mid.
6 We use left < right (not left <= right) because:
Answer: We're finding a value, not searching for a target
We're narrowing down to the minimum. When left == right, that's our answer. No need to check equality.

Solution

def findMin(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            # Minimum is in right half
            left = mid + 1
        else:
            # Minimum is at mid or left of mid
            right = mid
    
    return nums[left]

Complexity Analysis

Time O(log n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Binary Search problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye