Back to main article
LC 153 First True Medium

Find Minimum in Rotated Sorted Array

The First True pattern on a non-obvious condition. The secret: compare every element to the last element to reveal the hidden boolean structure.

Problem

What are we solving?

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array nums of unique elements, return the minimum element. You must write an algorithm that runs in O(log n) time.

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 (not rotated)
Input:nums = [1, 2, 3, 4, 5]
Output:1
Intuition

Revealing the hidden F→T pattern

A rotated sorted array looks chaotic at first glance. But it has a clean structure: it consists of exactly two sorted segments joined together. The minimum is always the first element of the second (smaller) segment — the exact point where the rotation happened.

Array: [4, 5, 6, 7, 0, 1, 2] — two sorted segments
upper4
upper5
upper6
upper7
lower0
lower1
lower2
Upper segment (large values) followed by lower segment (small values). Minimum = first element of lower segment.

The trick is finding a condition that separates these two segments. Comparing each element to the last element works perfectly:

Array: [4, 5, 6, 7, 0, 1, 2] · last = 2
condition: nums[i] <= nums[last]
4<=2?F
5<=2?F
6<=2?F
7<=2?F
0<=2?T*
1<=2?T
2<=2?T
First T is at index 4, value 0 — that's the minimum. Binary search finds it in O(log n).
Edge case: array not rotated [1, 2, 3, 4, 5] · last = 5
condition: nums[i] <= nums[last]
1<=5?T*
2<=5?T
3<=5?T
4<=5?T
5<=5?T
All T — first T is index 0, value 1. The minimum is correctly identified with no special casing needed.

Step-by-step walkthrough

Array: [4, 5, 6, 7, 0, 1, 2]

1
left=0, right=6 → mid=3, nums[3]=7, last=2

7 <= 2? No → condition FALSE. The minimum is in the right half. left = 4.

2
left=4, right=6 → mid=5, nums[5]=1, last=2

1 <= 2? Yes → condition TRUE. Save boundary=5, search left: right = 4.

3
left=4, right=4 → mid=4, nums[4]=0, last=2

0 <= 2? Yes → condition TRUE. Save boundary=4, search left: right = 3.

4
left=4 > right=3 → loop ends

Return nums[boundary] = nums[4] = 0. Correct!

→

Why compare with last and not first? The last element is always in the lower sorted segment. So anything <= last is also in the lower segment. If you compared with the first element, you'd be comparing against the upper segment which doesn't give a clean boundary.

Solution

Clean implementation

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int boundary = 0;
        int last = nums[nums.length - 1];

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] <= last) {
                // In lower sorted segment — could be the minimum
                boundary = mid;
                right = mid - 1; // search left for an earlier entry
            } else {
                // In upper sorted segment — minimum is to the right
                left = mid + 1;
            }
        }

        return nums[boundary];
    }
}
class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        boundary = 0
        last = nums[-1]

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] <= last:
                # In lower sorted segment — could be the minimum
                boundary = mid
                right = mid - 1  # search left for an earlier entry
            else:
                # In upper sorted segment — minimum is to the right
                left = mid + 1

        return nums[boundary]

Complexity

Time
O(log n)
Halves search space each iteration. The rotation doesn't affect the asymptotic bound.
Space
O(1)
Constant extra space — just pointers and one cached value.
→

Connection to LC 154: The next problem (LC 154) adds duplicate elements to this exact scenario. The core logic is identical — but you need an extra step to handle ties in the comparison. See the LC 154 page for the modification.

↑ Pattern map