# Rotated Array Minimum Search

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

If

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

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

If

$$
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

```id="rot-min-1"
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:

```id="rot-min-dup"
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

```id="py-rot-min"
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
```

```id="go-rot-min"
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
}
```