Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input array was originally sorted in ascending order, then rotated. For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].

All values are unique, and the task is to return the smallest value in O(log n) time.

The smallest value is exactly where the rotation “breaks” the sorted order. In an unrotated array, the first value is the minimum. In a rotated array, the minimum is the first value of the lower sorted block.

The key insight

A rotated sorted array is made of two sorted blocks:

  • the left block contains larger values
  • the right block contains smaller values

For [4, 5, 6, 7, 0, 1, 2], the blocks are:

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

The minimum is the first value of the second block.

Binary search works because comparing nums[mid] with nums[right] tells which side contains the minimum:

  • If nums[mid] <= nums[right], then mid ... right is already sorted, so the minimum is at mid or to the left.
  • If nums[mid] > nums[right], then mid is in the larger left block, so the minimum must be to the right of mid.

That lets each step discard half the search range while preserving the true minimum.

How to derive the optimal solution

Start with the brute-force idea: scan the array and return the first value that is smaller than the value before it. That works, but it is O(n), and the problem specifically asks for O(log n).

To get logarithmic time, ask what comparison can reveal a whole half of the array. The most useful anchor is the rightmost value in the current search window.

If the middle value is less than or equal to the rightmost value, the right side is sorted in normal ascending order. Since a sorted right side cannot hide a smaller value after mid, the minimum is either mid itself or somewhere on the left.

If the middle value is greater than the rightmost value, the middle value belongs to the larger block before the rotation point. The smaller block must begin somewhere to the right, so the minimum is strictly after mid.

Repeat until the search window has one index left. That index is the minimum.

Python solution

from typing import List, Sequence


def find_rotated_minimum(numbers: Sequence[int]) -> int:
    """
    Return the minimum value in a rotated sorted array with unique values.

    The input must contain at least one value. The array may be rotated back
    to its original sorted order, so the minimum can still be at index 0.
    """
    if not numbers:
        raise ValueError("numbers must contain at least one value")

    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        middle_index = left_index + (right_index - left_index) // 2

        if numbers[middle_index] <= numbers[right_index]:
            # The right side is sorted, so the minimum is at middle_index
            # or somewhere to its left.
            right_index = middle_index
        else:
            # middle_index is in the larger left block, so the minimum is
            # strictly to its right.
            left_index = middle_index + 1

    return numbers[left_index]


class Solution:
    def findMin(self, nums: List[int]) -> int:
        return find_rotated_minimum(nums)

Why this works

The algorithm maintains a search window that always contains the minimum.

When numbers[middle_index] <= numbers[right_index], the segment from middle_index through right_index is sorted. In that case, every value after middle_index is at least numbers[middle_index], so nothing to the right of middle_index can be the minimum. Keeping middle_index is important because it might be the answer.

When numbers[middle_index] > numbers[right_index], the middle value is larger than the right endpoint, so the rotation break must be somewhere to the right of middle_index. The minimum cannot be at middle_index or to its left inside the current larger block, so the search can move to middle_index + 1.

Each step removes about half of the remaining positions, so the time complexity is O(log n). The algorithm stores only two indexes and a midpoint, so the extra space complexity is O(1).

Interview follow-ups

What if the array can contain duplicates?

With duplicates, the comparison against the right endpoint can become ambiguous. For example, if nums[mid] == nums[right], the minimum could be on either side because equal values do not reveal which block mid belongs to.

The standard approach is to shrink the right boundary by one when the values are equal. If nums[mid] < nums[right], move right to mid. If nums[mid] > nums[right], move left to mid + 1. If they are equal, do right -= 1.

That still works because removing one copy of a duplicated right endpoint cannot remove the only minimum unless nums[right] itself equals the minimum and another equal value remains inside the window. The tradeoff is complexity: the worst case degrades to O(n), such as an array full of the same value, because equality may only shrink the window one position at a time.

How would you return the index of the minimum instead of the value?

The binary search already converges on the index of the minimum. Instead of returning numbers[left_index], return left_index.

This is useful when the interviewer cares about the rotation count. In this problem’s rotation convention, the index of the minimum is also the number of elements moved from the front to the back in the equivalent left-rotation view, and it identifies the pivot that splits the two sorted blocks.

The time and space complexities stay the same: O(log n) time and O(1) extra space.

Could you solve this by first checking whether the current window is already sorted?

Yes. At any point, if numbers[left_index] <= numbers[right_index], then the current window is already sorted and numbers[left_index] is the minimum inside that window.

Adding that check can make already-sorted or partially narrowed cases finish earlier. It does not change the worst-case complexity, because a genuinely rotated window still needs binary search steps. The clean endpoint-comparison version usually does not need this optimization, but it is a reasonable interview variation.

Why compare with the right endpoint instead of the left endpoint?

Comparing with the right endpoint gives a direct answer about whether the middle value is in the smaller sorted block or the larger sorted block.

Left-endpoint comparisons can also be made to work, but they are easier to get wrong around the unrotated case. For example, in [1, 2, 3, 4, 5], the middle value is greater than the left endpoint even though the minimum is not to the right. Using the right endpoint avoids that trap because if nums[mid] <= nums[right], the algorithm safely keeps the left side, including mid.

What if the interviewer asks for a two-phase solution?

A valid two-phase approach is to first find the pivot index with this same binary search, then use that pivot for whatever comes next. For this problem, the second phase is unnecessary because the pivot value is already the answer.

Two-phase thinking is more useful for related problems like searching for a target in a rotated sorted array. There, finding the pivot first can turn the array into two normal sorted ranges, after which a standard binary search can be run on the appropriate half.

Practical takeaway

The pattern is to look for the sorted half, then discard the half that cannot contain the rotation break.

For this problem, the right endpoint is the clean reference point. It tells whether the middle value is already in the smaller sorted block or still in the larger block before the pivot. Once that comparison is clear, the solution is just ordinary binary search with slightly different boundary updates.