Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Searching

Rotated Array Search Visualiser

Binary search where the sorted array has been cut and swapped.

Search forTarget: 39

This array was sorted and then rotated, so it is in two sorted runs. Look for 39 without unrotating it.

Comparisons
0
for scale
log₂n ≈ 5
AverageO(log n)extra space O(1)

Each round still halves the range, but spends several comparisons doing it: which half is in order, then whether the target lies inside it. The count is a small multiple of log₂n. The counter is an exact count for this run; the curve beside it is the shape that count follows as n grows, not a limit on it.

  • Being compared
  • Being written
  • Pivot or smallest so far
  • In its final place
  • Ruled out
function searchRotated(a, target) {
let lo = 0, hi = a.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (a[mid] === target) return mid;
if (a[lo] <= a[mid]) {
// the left half is in order
if (a[lo] <= target && target < a[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
// the right half is in order
if (a[mid] < target && target <= a[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1; // not here
}

The highlighted line is the one that produced the picture on the left.

What Rotated Array Search does

A rotated sorted array is a sorted array cut at some point and the two pieces swapped, so it climbs, drops once, then climbs again. Plain binary search breaks on it, because the value at mid no longer tells you which side the target is on. The fix is small: before choosing a side, work out which half is still in plain sorted order.

How it works, step by step

  1. Take mid as usual. If it is the target, stop.
  2. Compare the value at lo with the value at mid. If lo is not bigger, the left half holds no break and is in order.
  3. Check whether the target falls inside that ordered half's range. If it does, search there; if it does not, it can only be in the other half.
  4. If the left half is not in order, the right half must be, so apply the same test to it instead.

What to watch for

  • Exactly one half is always in plain sorted order, however the array was rotated. The break can only be on one side of mid.
  • The bracket marks the half that is in order, and the half that is discarded is greyed out — the same halving as plain binary search, so the comparison count stays around log₂n.
  • Being inside the ordered half's range is checked with both ends, not just one. Dropping either end of that test is the usual bug.

Cost

Best caseO(1)
AverageO(log n)
Worst caseO(log n) — distinct values
Extra spaceO(1)
Needs sortingSorted, then rotated

When to reach for it

Whenever sorted data has been rotated — a circular buffer, a log that wraps, a sorted list read starting from an arbitrary offset. The broader lesson is the one to take away: if you can find any ordered part, you can still halve.

Read more