Modified Binary Search Example: Searching an Array That Was Rotated

A sorted array turned round at an unknown point still has one sorted half at every mid, and the target either lies inside that half's range or does not.

A rotated sorted array can still be binary searched, because at every mid one of the two halves is sorted, and a sorted half says for certain whether the target lies inside it. A rotated array is a sorted one whose front part has been moved to the back: 4 9 14 18 22 27 31, rotated by three, becomes 22 27 31 4 9 14 18. The values are no longer in order overall, so "the value at mid is at least the target" is not monotone, yet each half of any range is either sorted or contains the point where the values drop. The task is to find 9.

With low at 0, mid at 3 and high at 6, which half is sorted?

The right half, from 4 to 18. The left half runs 22 27 31 4 and contains the drop from 31 to 4, so it is not sorted. The test is whether values[low] ≤ values[mid]: here 22 ≤ 4 is false, so the left half holds the drop and the right half is sorted.

Once the sorted half is known, its first and last values bound everything inside it, so the target is in that half exactly when it lies between them. If it is, the search keeps that half; otherwise it keeps the other half, which holds the drop and is searched the same way next round. This search ends as soon as mid holds the target, so it uses the form that runs while low ≤ high and moves past mid on both sides, rather than the first-true template.

Searching 22 27 31 4 9 14 18 for 9

Inputvalues 22 27 31 4 9 14 18, target 9

mid 3 holds 4, right half sorted
1. 22low
2. 27
3. 31
4. 4mid
5. 9
6. 14
7. 18high
22 is not at most 4, so the right half 4 to 18 is sorted, and 9 lies between 4 and 18: low moves to 4
mid 5 holds 14, left half sorted
1. 22
2. 27
3. 31
4. 4
5. 9low
6. 14mid
7. 18high
9 is at most 14, so the left half 9 to 14 is sorted, and 9 lies between 9 and 14: high moves to 4
mid 4 holds 9
1. 22
2. 27
3. 31
4. 4
5. 9lowmidhigh
6. 14
7. 18
mid holds 9, the target

Result9 is at index 4, found in three rounds.

The listing runs the search for a value in the right part, one in the left part, and one that is not there at all.

rotated.pypy

def search_rotated(values: list[int], target: int) -> int:
    low, high = 0, len(values) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if values[mid] == target:
            return mid
        if values[low] <= values[mid]:
            if values[low] <= target < values[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if values[mid] < target <= values[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1


values = [22, 27, 31, 4, 9, 14, 18]
for target in (9, 27, 20):
    print(f"{target}: index {search_rotated(values, target)}")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

9: index 4
27: index 1
20: index -1

It finds 9 at index 4 and 27 at index 1, and returns −1 for 20, which falls in the gap between 18 and 22. Each round discards half the range, so the search is O(log n) time and O(1) space. The test uses ≤ rather than <, because when low equals mid the one-value left half counts as sorted. If the array may hold repeated values, as in 3 3 1 3, values[low] = values[mid] no longer names a sorted half, and the worst case falls to O(n).

Binary Search

← → move through sections and cards