Rotated Array Search

Rotated array search finds a target value in an array that was originally sorted, then rotated around some pivot. The array still contains two sorted regions, but the smallest element may no longer be at index $0$.

For example:

may become:

The goal is to keep logarithmic search time without first undoing the rotation.

Problem

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

If no such index exists, return $-1$.

Assume first that all values are distinct.

Key Idea

At every step of binary search, at least one half of the current interval is sorted.

Let $m$ be the midpoint.

If

then the left half $[l, m]$ is sorted.

Otherwise, the right half $[m, r]$ is sorted.

Once we know which half is sorted, we can decide whether $x$ lies inside that half and discard the other half.

Algorithm

rotated_array_search(A, x):
    l = 0
    r = length(A) - 1

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

        if A[m] == x:
            return m

        if A[l] <= A[m]:
            # left half is sorted
            if A[l] <= x and x < A[m]:
                r = m - 1
            else:
                l = m + 1
        else:
            # right half is sorted
            if A[m] < x and x <= A[r]:
                l = m + 1
            else:
                r = m - 1

    return -1

Example

Let

and

Steps:

Return index $4$.

Correctness

At each iteration, the algorithm preserves this invariant:

• If $x$ exists in the array, then it lies in the current interval $[l, r]$.

The midpoint splits the interval into two halves. Since the original array was sorted and then rotated once, at least one half is sorted.

If the left half is sorted, the algorithm checks whether $x$ lies between $A[l]$ and $A[m]$. If yes, the right half cannot contain $x$. If no, the left half cannot contain $x$.

The same reasoning applies symmetrically when the right half is sorted.

Each iteration removes a half that cannot contain the target. Therefore, if the target is present, it is eventually found. If the interval becomes empty, no valid index exists.

Complexity

Space:

Handling Duplicates

With duplicates, the test for the sorted half can become ambiguous. For example:

In that case, the algorithm cannot determine which half is sorted from boundary values alone.

A common fix is to shrink both ends:

if A[l] == A[m] and A[m] == A[r]:
    l = l + 1
    r = r - 1

This preserves correctness but can degrade the worst-case time to:

When to Use

Use rotated array search when:

• the array was sorted and rotated
• random access is available
• values are distinct, or duplicates are acceptable with worst-case fallback
• logarithmic search is desired

Implementation

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

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

        if a[m] == x:
            return m

        if a[l] <= a[m]:
            if a[l] <= x < a[m]:
                r = m - 1
            else:
                l = m + 1
        else:
            if a[m] < x <= a[r]:
                l = m + 1
            else:
                r = m - 1

    return -1

func RotatedArraySearch(a []int, x int) int {
    l, r := 0, len(a)-1

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

        if a[m] == x {
            return m
        }

        if a[l] <= a[m] {
            if a[l] <= x && x < a[m] {
                r = m - 1
            } else {
                l = m + 1
            }
        } else {
            if a[m] < x && x <= a[r] {
                l = m + 1
            } else {
                r = m - 1
            }
        }
    }

    return -1
}