4.11.4 — Find Minimum in Rotated Sorted Array

LeetCode 153 · Medium · ★ Blind 75

The problem

A sorted array of distinct values has been rotated some number of times. Find the minimum in O(\log n).

[3,4,5,1,2]        →  1     (originally [1,2,3,4,5], rotated 3 times)
[4,5,6,7,0,1,2]    →  0
[11,13,15,17]      →  11    (rotated 0 times — still sorted)

The pattern

A rotated sorted array is always two sorted runs, with one drop between them:

[4, 5, 6, 7, 0, 1, 2]
 └── run A ──┘└run B┘
              ↑
        the minimum sits exactly here, at the drop

Everything in run A is larger than everything in run B. So the minimum is the first element of run B, which is the one place where a value is smaller than the value before it.

Now the binary search question: given mid, which run is it in, and which way is the minimum?

Compare nums[mid] with nums[high], the last element.

• If nums[mid] > nums[high], then mid is in run A — the high part. The drop must be somewhere to the right of mid, so search mid + 1 … high.
• If nums[mid] <= nums[high], then mid is in run B, the part containing the minimum. The minimum is at mid or to its left, so search low … mid.

Why compare with high and not with low

This is the detail worth getting right, because comparing with nums[low] is the more natural instinct and it breaks.

Take [3, 1, 2]. Here low = 0, high = 2, mid = 1. So nums[mid] = 1.

• Against high: 1 <= 2, so search left, low … mid. Correct — the minimum is at index 1.
• Against low: 1 < 3, which tells you mid is in the lower run… and that is also correct here, but on [1, 2, 3] (not rotated at all) the comparison with low gives 2 > 1, suggesting the minimum is to the right. It is not. The unrotated case breaks it.

Comparing against nums[high] handles the unrotated case for free, because then the whole array is run B and every comparison sends you left, converging on index 0.

Use the right-hand end. It is one character different and one whole class of bug smaller.

The solution

Python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1

        while low < high:                       # boundary search
            mid = low + (high - low) // 2
            if nums[mid] > nums[high]:
                low = mid + 1                   # minimum is strictly right of mid
            else:
                high = mid                      # mid could BE the minimum

        return nums[low]

TypeScript

function findMin(nums: number[]): number {
  let low = 0, high = nums.length - 1;

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] > nums[high]) low = mid + 1;
    else high = mid;
  }

  return nums[low];
}

This is shape B again — the boundary search from 4.11.1.

while low < high, and the loop ends with both pointing at the answer. There is no equality test, because you are not looking for a value, you are converging on a position.

high = mid, not mid - 1. When nums[mid] <= nums[high], mid itself might be the minimum, so it stays in the range.

No separate check for an unrotated array. Many published solutions add if nums[low] < nums[high]: return nums[low] as a shortcut. It is not needed — the loop already handles it, since every comparison sends high leftwards until it reaches index 0.

Trace

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

low	high	mid	nums[mid] vs nums[high]	action
0	6	3	7 > 2	low = 4
4	6	5	1 ≤ 2	high = 5
4	5	4	0 ≤ 1	high = 4

low == high == 4, so the answer is nums[4] = 0. ✓

Complexity

O(\log n) time, O(1) space.

What duplicates do to this

Find Minimum in Rotated Sorted Array II (LeetCode 154) allows repeats, and it breaks the algorithm in one specific place.

When nums[mid] == nums[high], you learn nothing. Consider [3, 3, 1, 3] and [3, 1, 3, 3] — both have nums[mid] == nums[high], and the minimum is on opposite sides.

The only safe move is high -= 1. That discards one duplicate without risking the minimum, because nums[high] has an equal twin at mid so it cannot be uniquely the smallest.

This makes the worst case O(n) — an array of all-equal values degrades to a linear scan. That degradation is unavoidable, and saying so is the correct answer. There is no O(\log n) algorithm when duplicates are allowed, because an adversary can hide the boundary behind identical values.

Where this goes next

• Search in Rotated Sorted Array — find a specific target rather than the minimum. That is 4.11.5, and one clean way to solve it is to find the rotation point with this code and then binary search the correct run.
• Peak Element (LeetCode 162) — the same idea on a different shape: compare nums[mid] with nums[mid+1] and move towards the higher side. It works on unsorted input, which surprises people, and it is a good demonstration that binary search only needs a rule that reliably discards half.

What the interviewer will push on

"Why compare against nums[high] and not nums[low]?" The unrotated case. Give [1, 2, 3].

"Why high = mid rather than mid - 1?" mid might be the minimum.

"What if the array is not rotated at all?" It works without a special case; trace it if asked.

"What if there are duplicates?" Fall back to high -= 1 on ties, and the worst case becomes O(n). Explain why that is unavoidable.

One thing to volunteer: describe the array as two sorted runs with one drop, and say that the minimum is exactly at the drop. That picture makes the comparison rule obvious instead of arbitrary.

Next: 4.11.5 Search in Rotated Sorted Array — the same broken array, now asked to find an arbitrary value in one pass.