Find Minimum in Rotated Sorted Array

The previous lesson searched a rotated list for a target. This one asks for its smallest value, which is also the rotation point: once you know where the smallest value is, you know how far the list was turned. It is shorter than the search, and it is a favourite follow-up because it needs a different comparison, and candidates who copy the previous lesson's test get it wrong.

The algorithm is the half-open boundary template from the core lesson. The only real decision is what to compare mid against.

The problem

A list of distinct integers was sorted in increasing order and then rotated between 1 and n times. Return its smallest value in O(log n) time.

• nums = [5, 6, 7, 1, 2, 3, 4] → 1. The list was [1, 2, 3, 4, 5, 6, 7], rotated so that 5, 6, 7 moved to the front.
• nums = [11, 13, 15, 17] → 11. Rotated n times, which leaves it unchanged.

Constraints: 1 ≤ len(nums) ≤ 5000, values distinct, between -5000 and 5000.

Clarifying questions

• Distinct values? Yes. (Duplicates are the follow-up.)
• Can the list be unrotated? Yes, and then the answer is the first value.
• Value or index? The value. The index comes for free.
• Empty list? No, at least one value.

Approach 1: the simple way

Walk the list and look for the drop — the one place where a value is smaller than the value before it. The value after the drop is the smallest. If there is no drop, the list is not rotated and the first value is the smallest.

1def find_min_linear(nums: list[int]) -> int:2    """Look for the one place where the order drops: O(n)."""3    for i in range(1, len(nums)):4        if nums[i] < nums[i - 1]:5            return nums[i]                   # the value right after the drop6    return nums[0]                           # no drop: the array is not rotated

Time: O(n). Space: O(1). (Python's min(nums) is the same cost.)

The problem requires O(log n). A scan needs up to 5,000 steps where binary search needs 13, and the interviewer is asking specifically whether you can find a boundary in data that is not fully sorted.

The key insight

Turn the question into a monotonic test. Look at every value and ask: "is this value at most the last value of the list?"

nums:                  5    6    7    1    2    3    4at most last (4)?      no   no   no   yes  yes  yes  yes

Values in the first run (before the drop) are all bigger than the last value, because the last value belongs to the second run, which holds the small numbers. Values in the second run are all at most the last value, because that run is sorted and ends there. So the answers read no, no, yes, yes, and the first yes is the smallest value. It is a first-true search.

The code does not have to compare with the original last value. Comparing nums[mid] with nums[right], the end of the current range, works the same way, because nums[right] always sits in the second run of whatever range is left:

• If nums[mid] > nums[right], mid is before the drop, and the drop is somewhere after mid. The minimum is strictly right of mid: left = mid + 1.
• Otherwise nums[mid..right] climbs with no drop, so nothing after mid is smaller than nums[mid]. The minimum is at mid or to its left: right = mid, keeping mid.

Why not compare with nums[left], as the search lesson did? Because it cannot tell two cases apart. In [1, 2, 3], nums[mid] = 2 is bigger than nums[left] = 1, which says "the left half is sorted" — true, but the minimum is in that sorted half, at index 0. In [3, 4, 5, 1, 2], nums[mid] = 5 is also bigger than nums[left] = 3, and there the minimum is on the right. Same comparison result, opposite answers. Put side by side:

The left-end column says the same thing for both arrays, so it cannot steer the search. The right-end column differs, and both times it points the right way. "Middle bigger than right end" always means the drop is to the right.

Approach 2: boundary search against the right end

1def find_min(nums: list[int]) -> int:2    """Smallest value in a rotated sorted array of distinct values."""3    left, right = 0, len(nums) - 14    # invariant: the minimum is inside nums[left..right]5    while left < right:6        mid = left + (right - left) // 27        if nums[mid] > nums[right]:8            left = mid + 1                   # a drop lies after mid, so the minimum does too9        else:10            right = mid                      # mid..right is sorted; mid may be the minimum11    return nums[left]

Dry run on [5, 6, 7, 1, 2, 3, 4]:

Step 1 lands on the answer but cannot know it yet, so it keeps index 3 in the range with right = mid. The next two steps close in from the left.

On the unrotated [11, 13, 15, 17]: mid = 1 (13 is not bigger than 17, right = 1), then mid = 0 (11 is not bigger than 13, right = 0), and the answer is 11. No special case needed.

Time: O(log n). Space: O(1). The loop uses while left < right and right = mid, the half-open boundary pattern: it stops when one candidate is left, and that candidate is the minimum.

Edge cases

• One element: the loop never runs; return it.
• Two elements [2, 1]: mid = 0, 2 is bigger than 1, so left = 1: answer 1. And [1, 2]: right = 0: answer 1.
• Not rotated: every comparison says "not bigger", so right walks down to 0.
• Rotated by one, like [2, 3, 4, 5, 1]: the minimum is last; every comparison moves left right until it gets there.

Follow-ups

• "Values can repeat." When nums[mid] == nums[right], you cannot tell which side the drop is on. But nums[right] has a copy at mid, so dropping right never loses the minimum's value:

1def find_min_with_duplicates(nums: list[int]) -> int:2    """Same search when values may repeat. Worst case O(n)."""3    left, right = 0, len(nums) - 14    while left < right:5        mid = left + (right - left) // 26        if nums[mid] > nums[right]:7            left = mid + 18        elif nums[mid] < nums[right]:9            right = mid10        else:11            right -= 1                       # cannot tell which side; drop one safe copy12    return nums[left]

The worst case is O(n): on [3, 3, 3, 1, 3] or all-equal input, most steps remove one element. Say this out loud; it is not a flaw in the code, because no algorithm can find a single 1 among 3s without looking.

• "Return how many times it was rotated." Return left (the index) instead of nums[left].
• "Find a peak element" (a value bigger than both neighbours, in an unsorted array). Also a compare-with-a-neighbour binary search: if nums[mid] < nums[mid + 1], a peak exists to the right, so left = mid + 1; otherwise right = mid.