Rotated Array Minimum Search

Rotated array minimum search finds the smallest element in a sorted array that has been rotated around an unknown pivot.

For example:

$$ [1, 3, 5, 7, 9] $$

may become:

$$ [7, 9, 1, 3, 5] $$

The minimum element is the rotation point.

Problem

Given a rotated sorted array $A$ of length $n$, find an index $i$ such that

$$ A[i] = \min(A) $$

Assume first that all values are distinct.

Key Idea

Compare the middle element with the right boundary.

$$ A[m] > A[r] $$

then the minimum lies strictly to the right of $m$.

$$ A[m] \le A[r] $$

then the minimum lies at $m$ or to the left of $m$.

This works because the right side tells us whether the midpoint is in the upper rotated part or the lower sorted part.

Algorithm

rotated_array_minimum_search(A):
    l = 0
    r = length(A) - 1

    while l < r:
        m = l + (r - l) // 2

        if A[m] > A[r]:
            l = m + 1
        else:
            r = m

    return l

Example

Let

$$ A = [7, 9, 11, 1, 3, 5] $$

Steps:

step	l	r	m	A[m]	A[r]	action
1	0	5	2	11	5	move right
2	3	5	4	3	5	move left
3	3	4	3	1	3	move left

Return index $3$.

The minimum value is:

$$ A[3] = 1 $$

Correctness

The algorithm maintains the invariant:

The minimum element lies in the current interval $[l, r]$.

If $A[m] > A[r]$, then $m$ lies in the upper part before the rotation point. Since $A[r]$ is smaller than $A[m]$, the minimum cannot be at $m$ or to its left, so the algorithm moves to $[m + 1, r]$.

If $A[m] \le A[r]$, then $m$ lies in the lower sorted part, or the interval is already normally sorted. The minimum may be at $m$ or to the left, so the algorithm moves to $[l, m]$.

The interval shrinks each iteration. When $l = r$, only the minimum index remains.

Complexity

case	time
distinct values	$O(\log n)$

Space:

$$ O(1) $$

Handling Duplicates

With duplicates, the comparison

$$ A[m] = A[r] $$

can be ambiguous. A safe fallback is to shrink the right boundary:

if A[m] == A[r]:
    r = r - 1

This preserves correctness but may degrade worst-case time to:

$$ O(n) $$

Use Cases

Find rotation pivot
Recover sorted order from rotated data
Search in rotated arrays
Detect smallest timestamp or key after cyclic shift

Implementation

def rotated_array_minimum_search(a):
    if not a:
        return -1

    l, r = 0, len(a) - 1

    while l < r:
        m = l + (r - l) // 2

        if a[m] > a[r]:
            l = m + 1
        else:
            r = m

    return l

func RotatedArrayMinimumSearch(a []int) int {
    if len(a) == 0 {
        return -1
    }

    l, r := 0, len(a)-1

    for l < r {
        m := l + (r-l)/2

        if a[m] > a[r] {
            l = m + 1
        } else {
            r = m
        }
    }

    return l
}