Workspace

Problem workspace

3 day streakD

Minimum in a Rotated Sorted Array

MediumBinary SearchRotations & structure

The challenge

Return the index of the minimum value in a rotated ascending array.

Distinct values. Empty input returns −1. This lesson returns an index; use nums[index] for the value.

Example

[4, 5, 6, 7, 0, 1, 2] → index 4, value 0.

Use the walkthrough below to inspect the input and each state change.

See Rotation minimum, step by step

Inspect the comparison, the invariant, and the next boundary.

Inclusive candidate indices
L = 0 · mid = — · R = 640516273041526
Current comparisonResolved positionNumbers below = indices
Left
0
Middle
—
Right
6
Step 01 / 5

Start with the candidate indices

The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.

left = 0; right = 6

Recorded result so far

Not resolved
View exact input

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

Put it into code

Compare nums[mid] with nums[right]. A middle larger than the right endpoint lies before the rotation break.

Indices are zero-based. C++ uses C++17 or later.

def rotated_minimum(nums):
    if not nums:
        return -1  # No minimum index.
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return left  # Return the minimum's INDEX.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap