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).

[11,13,15,17]      →  11    (rotated 0 times — still sorted)

To put this in plain English: you are given a list of numbers that was originally sorted in ascending order. Then, somebody took a chunk from the end and moved it to the beginning. You need to find the smallest number in this list, and you must do it quickly (O(\log n) time).

Constraints to Keep in Mind:

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• All values in nums are unique.
• nums is sorted and rotated between 1 and n times.

The Brute Force Approach

The most naive way to solve this is a linear scan.

• How it works: You write a simple for loop, iterating from left to right, keeping track of the smallest number seen so far (min_val = min(min_val, nums[i])). Or you could even sort it and pick the first element.
• Why it's too slow: A linear scan takes O(n) time. Sorting takes O(n \log n) time. The problem explicitly requires O(\log n) time, which means we must discard half the array at each step without looking at it. That implies binary search.

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];
}

Code Walkthrough

1. low, high = 0, len(nums) - 1: Set pointers to the very ends of the array.
2. while low < high:: Loop continues until low and high converge on the same index.
3. mid = low + (high - low) // 2: Calculate the middle index safely to avoid integer overflow.
4. if nums[mid] > nums[high]:: If the middle element is greater than the rightmost element, the "drop" (the minimum) must be to the right. We discard the left half and mid itself by setting low = mid + 1.
5. else:: Otherwise, nums[mid] is less than or equal to nums[high]. The minimum is at mid or to its left. We discard the right half but keep mid by setting high = mid.
6. return nums[low]: By the end of the loop, low and high point to the exact same index, which is guaranteed to be the minimum.

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. ✓

Let's do another trace on an unrotated array [1, 2, 3] to prove it works:

• low = 0, high = 2. mid = 1. nums[1] = 2, nums[2] = 3.
• 2 <= 3, so high = mid = 1.
• low = 0, high = 1. mid = 0. nums[0] = 1, nums[1] = 2.
• 1 <= 2, so high = mid = 0.
• Loop breaks (low == high == 0). Returns nums[0] = 1. ✓

Complexity

• Time Complexity: O(\log n). At each step, we divide the search space in half. For an array of size n, this requires at most \log_2(n) steps. Since each step is just indexing and comparing (which takes O(1) time), the total time is strictly logarithmic.
• Space Complexity: O(1). We only use three integer variables (low, high, mid), which requires constant space regardless of the array's size.

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.