Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array is LeetCode 153, and it is one of those problems that teaches you binary search is about more than just "find a target." There is no target here. You are looking for the inflection point, the spot where the array wraps around. And you can find it in O(log n) using the same binary search pivot logic you already know.

If you have solved Search in Rotated Sorted Array (LeetCode 33), this is actually the simpler version. Instead of searching for a specific value in a rotated array, you are just finding where the rotation happened. That rotation point is the minimum.

The problem

You are given a sorted array of unique integers that has been rotated between 1 and n times. Find the minimum element. You must solve it in O(log n) time.

Example: nums = [3, 4, 5, 1, 2]. The original sorted array was [1, 2, 3, 4, 5], and it was rotated 3 times. The minimum is 1.

The minimum always sits at the binary search pivot, the exact point where the sorted order breaks. On the left side of the pivot, values are larger. On the right side, values restart from the smallest. Finding that pivot is the whole problem.

Why you cannot just scan

Sure, you could loop through the array in O(n) and track the smallest value. But the problem requires O(log n). That means you need to cut the search space in half at each step. The array is almost sorted, which is a strong hint that binary search applies.

The question is: what condition do you use to decide which half to keep?

The key insight: compare mid to the right boundary

In a rotated sorted array, you can figure out which side the minimum is on by comparing nums[mid] to nums[hi].

• If nums[mid] is greater than nums[hi], the rotation break is somewhere to the right of mid. The minimum must be in the range [mid + 1, hi].
• If nums[mid] is less than or equal to nums[hi], the right half is sorted and has no break. The minimum is at mid or to the left: [lo, mid].

That is it. One comparison per step, and you throw out half the array.

Visual walkthrough

Let's find the minimum in [3, 4, 5, 1, 2] step by step using binary search on the pivot.

Two real comparisons. Out of 5 elements, we found the minimum in O(log n) time. The search space shrinks by half at each step until only one element remains.

The code

Here is the complete Python solution for LeetCode 153, find minimum in rotated sorted array:

def find_min(nums):
    lo, hi = 0, len(nums) - 1

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid

    return nums[lo]

Let's break this down.

The loop condition is lo < hi, not lo <= hi. This is important. We are not looking for a target where we might return early. We are narrowing down to a single index. When lo == hi, we have found it.

mid = lo + (hi - lo) // 2 is the standard overflow-safe midpoint calculation, identical to the binary search template.

if nums[mid] > nums[hi] means the rotation break is to the right of mid. The minimum cannot be at mid (it is bigger than something to its right), so we safely set lo = mid + 1.

else: hi = mid means mid could be the minimum, or the minimum is to the left. We cannot skip mid, so we set hi = mid (not mid - 1).

Why compare to nums[hi] and not nums[lo]?

This trips people up. Why not compare nums[mid] to nums[lo] like you do in Search in Rotated Sorted Array?

Consider the array [1, 2, 3, 4, 5] (not rotated at all). If you check nums[mid] > nums[lo], that is 3 > 1, which is true. You would set lo = mid + 1 and skip right past the actual minimum at index 0.

Comparing to nums[hi] avoids this. nums[mid] > nums[hi] is 3 > 5, which is false. You correctly keep the left half and converge on the minimum.

The nums[hi] comparison works in all cases: rotated arrays, and arrays that were not rotated at all.

Complexity analysis

Time: O(log n). Each step eliminates half the search space. The loop runs at most log2(n) times.

Space: O(1). Three variables: lo, hi, mid. No extra data structures.

This matches the problem's requirement and is optimal. You cannot locate the pivot in fewer than O(log n) comparisons.

Edge cases to watch for

• Not rotated: nums = [1, 2, 3, 4, 5]. The minimum is at index 0. nums[mid] is never greater than nums[hi], so hi keeps moving left until lo == hi == 0. Works correctly.
• Single element: nums = [1]. lo == hi from the start, so the loop never runs. We return nums[0].
• Two elements: nums = [2, 1]. mid = 0, nums[0] = 2 > nums[1] = 1, so lo = 1. Now lo == hi, return nums[1] = 1.
• Rotated by one: nums = [5, 1, 2, 3, 4]. The minimum is at index 1. The first comparison sees nums[2] = 2 which is less than nums[4] = 4, so hi = 2. Then nums[1] = 1 which is less than nums[2] = 2, so hi = 1. Then lo == hi == 1. Correct.

The building blocks

This problem is built on one core building block: binary-search-template.

The skeleton is exactly the standard binary search: maintain [lo, hi], compute mid, eliminate half the range. The only thing that changes is the decision logic. Instead of comparing nums[mid] to a target, you compare nums[mid] to nums[hi] to decide which half contains the rotation break.

# Standard binary search (find target):
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

# Find minimum in rotated array:
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1
    else:
        hi = mid

Two small differences: the loop condition (< vs <=) and the comparison (nums[mid] vs target becomes nums[mid] vs nums[hi]). If you can write the binary search template from memory, this problem is just swapping out the comparison.

This "binary search on a property" pattern shows up in several related problems:

• Search in Rotated Sorted Array (LeetCode 33): search for a target in the same structure, using the sorted-half check
• Find Peak Element (LeetCode 162): binary search where you compare mid to its neighbor
• Find Minimum in Rotated Sorted Array II (LeetCode 154): same idea but with duplicates, worst case O(n)

From understanding to recall

The logic here is clean: compare mid to hi, go right if mid is bigger, shrink left otherwise. Simple enough to understand in one sitting.

But in an interview, when you are also thinking about edge cases and time pressure is mounting, the details slip. Was it lo < hi or lo <= hi? Do you set hi = mid or hi = mid - 1? Do you compare to nums[lo] or nums[hi]? These small choices are the difference between a correct solution and an infinite loop.

Spaced repetition solves this. You type the solution from scratch today, then again tomorrow, then in three days. By the fourth repetition, the while lo < hi and hi = mid are muscle memory. You are not deriving them from scratch under pressure. You just know.

LeetCode 153 is a perfect candidate for SRS drilling because the code is short but the decisions are subtle. Get it into long-term memory once, and every rotated-array variant becomes easier.

Related posts

• Search in Rotated Sorted Array (LeetCode 33): Modified Binary Search - Uses the same rotated structure but searches for a specific target instead of the minimum
• Binary Search (LeetCode 704): The Foundation - Master the standard binary search template first, then this pivot variant becomes a small modification on top