Find Minimum in Rotated Sorted Array: Hunting the Seam

If you interview at Amazon, Meta, Goldman Sachs, expect some version of "Find Minimum in Rotated Sorted Array". It is rated Medium, and it falls squarely into the Modified Binary Search pattern — pattern-first preparation beats grinding random problems every time. Part 5 of 11 in the Modified Binary Search arc.

The Problem

Given a rotated sorted array of distinct values, return its minimum element in O(log n). The minimum is the rotation seam, so this is really find-the-pivot — the building block for the two-pass approach to rotated search.

Input:  nums = [3, 4, 5, 1, 2]
Output: 1

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

No target value exists to compare against — instead the predicate is positional: elements at or after the seam are all at most nums[-1], elements before it are all greater. A monotonic predicate over indices means boundary binary search, with the right edge as the fixed reference.

The Approach

Compare nums[mid] against nums[hi]. Greater means the seam lies strictly right of mid — jump lo = mid + 1. Otherwise mid could itself be the minimum, so hi = mid keeps it. The range shrinks to a single index: the seam.

Why compare against the right edge and not the left? Because equality with the left is ambiguous when the array is not rotated at all. The right-edge comparison has no such blind spot with distinct values — that reasoning is the interview.

Python Solution

def find_min(nums: list[int]) -> int:
    """Minimum of a rotated sorted array of distinct values."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1               # seam is strictly right of mid
        else:
            hi = mid                   # mid could be the minimum
    return nums[lo]

Complexity

• Time: O(log n) — the candidate range halves each step
• Space: O(1) — two indices

Interview Tips and Follow-Ups

• The not-rotated array ([11, 13, 15, 17]) is the planted case — right-edge comparison handles it silently; left-edge comparison does not.
• Duplicates (Find Minimum II) degrade the guarantee: on equality with nums[hi], decrement hi and accept O(n) worst case.
• Returning the index instead of the value turns this into the pivot-finder for two-pass rotated search — one question, two deliverables.

More Modified Binary Search problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.