Algorithm

Find Minimum in Rotated Sorted Array

mediumBinary Search
Binary Search Pattern

Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array.

CONSTRAINTS
  • n == nums.length, 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All integers in nums are unique
EXAMPLE 1
Input: nums = [3,4,5,1,2]
Output: 1
EXAMPLE 2
Input: nums = [4,5,6,7,0,1,2]
Output: 0
What if the array is not rotated at all?
An unrotated array is basically rotated by 'N' steps. The first element is still the minimum, and the algorithm will correctly converge to index 0.

A rotated sorted array is a strange landscape: it's not one single mountain, but two separate ascending slopes separated by a "Cliff."

The Brute Force Search

The most obvious way is to scan the array from left to right. You look for the moment a number becomes smaller than the one before it. That drop-off point is your minimum.
- The Cost: If the minimum is at the very end of a 10,000-element array, you've done 10,000 checks. This is O(N) efficiency.

The Cliff Discovery

Because we have two sorted slopes, any guess in the middle tells us exactly where the "Cliff" (the minimum) is hiding.

Discovery: Compare your Midpoint to the Right Boundary.
1. If Mid > Right: You are standing on the "High Slope." The cliff must be somewhere to your right. You can safely discard the entire high ground you are standing on.
2. If Mid < Right: You are standing on the "Low Slope." The absolute minimum is either exactly where you are, or somewhere to your left. You can discard everything further down the slope to your right.

Code Blueprint
text
left = 0
right = length - 1

WHILE left < right:
    mid = left + (right - left) / 2
    
    // Compare mid to the absolute right boundary
    IF nums[mid] > nums[right]:
        // We are on the high slope, jump to the right
        left = mid + 1
    ELSE:
        // We are on the low slope, the min is at or left of mid
        right = mid

RETURN nums[left]
Why the Pattern is King

Binary Search is the perfect tool for "Rotated" problems because it allows us to identify which segment of the array we are in using just one comparison. We don't need to find the "pivot" point first; by comparing against the boundaries, we let the search window naturally collapse around the cliff-drop until only the minimum remains.

Interactive Strategy Visualization

Finding the Pivot Point

The minimum element is the only one that is smaller than its previous element. We find this "cliff" by comparing Mid against Right.

3Left
4
5
1
2Right
📉
Searching for the cliff...

O(N) linear scan
→
O(log N) binary search