Module 12 · Binary Search and Monotone Answer Spaces

117. Find Minimum in Rotated Sorted Array

Bridge · Download this solution · All solutions and shared helpers

Problem

Return the smallest value in a nonempty rotation of a strictly increasing integer array. Distinctness is guaranteed; an unrotated array is allowed. Use a half-open binary search and do not scan for the descending edge.

Examples

Example 1

rotated_minimum([15,18,20,1,3,5,8,9,13])
=> 1

The first value in the low block is the minimum.

Example 2

rotated_minimum([1,2,3])
=> 1

All predicate values are true when unrotated.

Example 3

rotated_minimum([7])
=> 7

The only candidate is also the last value.

Reveal the worked solution and reasoning

Why this mechanism works

Compare every candidate with the fixed final array value. Values in the rotated high block are greater than it; values in the low block are <= it. The predicate nums[i]<=nums[-1] is therefore false then true, and its first true index is the minimum. For an unrotated array, it is true everywhere.

State and boundaries

last is fixed for the whole search. left and right bound the first index whose value is<=last.

Protocol

Remember the final value.
Run a first-true search on nums[mid]<=last.
Move right to mid on True.
Move left to mid+1 on False.
Return the value at the boundary.

Visualization

[15,18,20,1,3,5,8,9,13], last=13
predicate <=13: F F F T T T T T T
first True points to 1

Python implementation

def rotated_minimum(nums):
    last = nums[-1]
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] <= last:
            right = mid
        else:
            left = mid + 1
    return nums[left]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

rotated_minimum([15,18,20,1,3,5,8,9,13])

L2 rotated_minimum: last = nums[-1]
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13

L3 rotated_minimum: left, right = 0, len(nums)
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=0; right=9

L5 rotated_minimum: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=0; right=9; mid=4

L7 rotated_minimum: right = mid
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=0; right=4; mid=4

L5 rotated_minimum: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=0; right=4; mid=2

L9 rotated_minimum: left = mid + 1
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=3; right=4; mid=2

L5 rotated_minimum: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=3; right=4; mid=3

L7 rotated_minimum: right = mid
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; last=13; left=3; right=3; mid=3

Result: 1. The first value in the low block is the minimum.

rotated_minimum([1,2,3])

L2 rotated_minimum: last = nums[-1]
nums=[1, 2, 3]; last=3

L3 rotated_minimum: left, right = 0, len(nums)
nums=[1, 2, 3]; last=3; left=0; right=3

L5 rotated_minimum: mid = (left + right) // 2
nums=[1, 2, 3]; last=3; left=0; right=3; mid=1

L7 rotated_minimum: right = mid
nums=[1, 2, 3]; last=3; left=0; right=1; mid=1

L5 rotated_minimum: mid = (left + right) // 2
nums=[1, 2, 3]; last=3; left=0; right=1; mid=0

L7 rotated_minimum: right = mid
nums=[1, 2, 3]; last=3; left=0; right=0; mid=0

Result: 1. All predicate values are true when unrotated.

Why the solution is correct

Strictly increasing source order separates the rotated high and low blocks relative to the final value. The minimum starts the low block, exactly the first true position. Standard monotone-boundary updates preserve that boundary and converge to it.

Time and space

O(log n) time and O(1) auxiliary space.

Common mistakes

Changing last to a moving boundary value changes the predicate and requires a different proof. An empty array has no minimum and is excluded by the contract.

Reasoning card

State: last is fixed for the whole search. left and right bound the first index whose value is<=last.

Invariant: The minimum remains inside [left,right].

Decision to rehearse: Compare middle with right to locate the unsorted boundary.

Finish: Return the value at the boundary

Transfer exercise

Return the rotation index instead of its value, then use it to map ordinary binary-search positions into the rotated array.