roadmap/binary-search/Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

MediumMicrosoftAmazonFacebookGoogle

Problem

Given a sorted rotated array of unique integers, find the minimum element in O(log n).

Intuition — the key insight

The minimum is at the rotation point. Key observation: if nums[mid] > nums[hi], the minimum is in the right half (mid is in the left sorted portion, which is entirely larger). Otherwise the minimum is in the left half including mid.

Approach

Binary search on the pivot

Compare nums[mid] to nums[hi]. If mid > hi, min is in [mid+1, hi]. Otherwise min is in [lo, mid]. When lo==hi, we've found the minimum.

Complexity

Time

O(log n)

Space

O(1)

Standard binary search — halves space each iteration.

Solution code

Python

def findMin(self, 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  # min is in right half
        else:
            hi = mid      # min is at mid or in left half
    
    return nums[lo]

Edge cases to remember

⚠Not rotated (already sorted): nums[0] is min, algorithm handles correctly

⚠Rotated by 1 position

⚠Single element: return it

Hints

What pattern do you think this problem uses?