Find Minimum in Rotated Sorted Array

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if it was rotated 4 times.
• [1,2,3,4,5,6] if it was rotated 6 times.

Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Approach

Use binary search on the rotated array. Compare the middle element with the rightmost element: if nums[mid] > nums[right], the minimum is in the right half; otherwise it is in the left half (including mid). Continue until left == right. This works for single-element and unrotated arrays.

Why It Works

In a rotated sorted array with unique elements, one half is always sorted and the minimum lies in the unsorted half. The comparison with nums[right] tells us which half contains the rotation point. Repeating this shrinks the search space to the minimum.

Complexity

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

Reference Implementation (Python)

class Solution:
    def findMin(self, nums: List[int]) -> int:
        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]