cf.completefrontend
SEARCHING & BINARY SEARCH · CORE

Binary search in a rotated list

Binary search a sorted list that was cut in two and swapped around, by checking which half is still in order.

Time O(log n)Space O(1)4 practice problemsStep-through picture

The idea

Take a sorted list like [3, 6, 9, 12, 15, 18, 22], cut it somewhere, and put the back part in front: [15, 18, 22, 3, 6, 9, 12]. This is a rotated sorted list. It is no longer sorted, so plain binary search fails. But it is still almost sorted: it is two sorted pieces, one after the other.

Here is the key fact. If you cut a rotated list at any middle index, at least one of the two halves is fully sorted. You can tell which one by comparing its first and last items. And in a sorted half, you can check in one step whether the target is inside it.

So each step does this: find the sorted half, ask "is the target inside it?", and keep that half or the other one. You still throw away half the list each time, so the search stays O(log n).

An everyday example

A clock face of numbered seats

Seats in a round theater are numbered in order, but the first seat is not at the door. Walking in, you see seats 15, 18, 22, then 3, 6, 9, 12. You need seat 6. You look at the seat in the middle of the row. Then you look at one side of it and see the numbers go up steadily with no jump. Is 6 between that side's first and last number? If yes, go that way. If not, it must be on the other side, the one with the jump.

How the example maps to the code
In the exampleIn the code
The row of seats, starting at the wrong placeThe rotated array items
The seat in the middleitems[mid]
A side where numbers go up with no jumpitems[low] <= items[mid] (left half sorted)
"Is my seat number between its ends?"items[low] <= target && target < items[mid]

From the slow way to binary search in a rotated list

  1. A rotated list like [24, 29, 33, 4, 9, 13, 17, 20] is not sorted, so the safe, obvious way is a linear scan: 8 checks here, n in general. A better way is to find the drop first, from 33 to 4, and then binary search the right piece. That works, but it needs two separate searches and two chances for an off-by-one bug.
  2. Look at what one middle check can tell you. A sorted list rotated once has only one drop. Cut it at mid, and the drop lands in one half at most. The other half has no drop, so it is fully sorted, and you can see which half that is by comparing its two ends: if items[low] <= items[mid], the left half is sorted.
  3. A sorted half is useful because you can test in one step whether target can be inside it: only if it lies between that half's first and last values. If it does, keep that half. If it doesn't, the target can only be in the other half, the one with the drop, even though you know little else about that half.
  4. Both choices throw away half the range, just like plain binary search. The half you keep is again a rotated list or a plain sorted one, so the same trick works on the next step. Check mid, find the sorted half, test the target against its ends, keep one half: that loop is binary search in a rotated list.

How it works

  1. Set low = 0 and high = items.length - 1, as in plain binary search.
  2. Pick mid. If items[mid] is the target, return mid.
  3. If items[low] <= items[mid], the left half from low to mid is sorted.
  4. In that case, if target is between items[low] and items[mid], search left (high = mid - 1). Otherwise search right (low = mid + 1).
  5. Otherwise the right half from mid to high is sorted. If target is between items[mid] and items[high], search right. Otherwise search left.
  6. If low passes high, the target is not there: return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function searchRotated(items, target) {
  2. let low = 0;
  3. let high = items.length - 1;
  4. while (low <= high) {
  5. const mid = Math.floor((low + high) / 2);
  6. if (items[mid] === target) return mid;
  7. if (items[low] <= items[mid]) {
  8. if (items[low] <= target && target < items[mid]) {
  9. high = mid - 1;
  10. } else {
  11. low = mid + 1;
  12. }
  13. } else {
  14. if (items[mid] < target && target <= items[high]) {
  15. low = mid + 1;
  16. } else {
  17. high = mid - 1;
  18. }
  19. }
  20. }
  21. return -1;
  22. }

How fast it is

TimeO(log n)
Extra memoryO(1)

Every loop throws away half of the range, just like plain binary search. With repeated values the halves can't always be told apart, and the search may have to shrink one step at a time.

  • Best caseO(1)

    The target is the first middle item, so the first check returns it.

  • Average caseO(log n)

    Distinct values and a target anywhere: half the range is dropped at every check.

  • Worst caseO(log n)

    Distinct values and a missing target: about log₂ n checks, 3 for the 8-item trace. With repeated values, the fixed version that shrinks both ends by one can need O(n).

Common mistakes

  • Writing items[low] < items[mid] instead of <=. When low equals mid, the left half is one item and sorted, but the test says it isn't, and the search goes the wrong way.
  • Using <= on both ends of the range check, like target <= items[mid]. The middle was already checked, so this can send the search toward mid when the target is elsewhere. Use strict < on the mid side.
  • Finding the rotation point first and then running two binary searches. It works, but it is twice the code and twice the chances for an off-by-one error.
  • Forgetting that a list rotated by 0 (fully sorted) is also a valid input. Test it.

When to use it

Look for these clues in a problem:

  • The list is described as sorted, then rotated, shifted, or wrapped around.
  • The data comes from a circular buffer that overwrites its oldest entries.
  • You need the smallest item, or the point where the order resets, in a list that is sorted except for one drop.
  • The problem asks for O(log n) even though the list is not fully sorted.

Check yourself

Answer each one in your head first, then open it.

Why is at least one half always sorted?

A rotated sorted list has at most one drop, and the drop can be in only one of the two halves. The half without the drop is sorted.

Why does the left-half test use items[low] <= items[mid] and not <?

When low === mid, the left half is one item, which is sorted. With < the code would treat the right half as sorted and can search the wrong side, as in [9, 4] with target 4.

If the target doesn't fit between the sorted half's ends, why must it be in the other half?

Every value in the sorted half lies between its ends, so the target can't be there. The promise says the target, if present, is between low and high, so only the other half is left.

About how many checks does it need for a rotated list of 1,000 distinct items?

About 10, the same as plain binary search, because each check still halves the range.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 4 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The promise is the same as in plain binary search: if target is anywhere in the list, it is somewhere from low to high. It is true at the start, when the range is the whole list, and it needs the values to be distinct.

Each step keeps it. If items[low] <= items[mid], the piece from low to mid has no drop, so its values run in order from items[low] to items[mid]. With distinct values, every item in the other half is either bigger than items[mid] or smaller than items[low]. So a target inside that span can only be in the sorted piece, and a target outside it can only be in the other piece. The same reasoning covers a sorted right half.

The loop ends because each step leaves mid out, so the range shrinks by at least one. When the range is empty, the promise says the target was never there, so -1 is right. With repeated values the half test can lie: in [2, 0, 2, 2, 2], items[0] <= items[2] is true even though the drop is on the left, and this code returns -1 for target 0.

Going deeper

3 more ideas

Why one half is always sorted

A rotated list has at most one drop, the place where a big value is followed by a small one. The middle index splits the list into a left half and a right half. The drop can be in only one of them, so the other half has no drop, which means it is sorted. If items[low] <= items[mid], there is no drop on the left, so the left half is the sorted one.

Finding the smallest item instead

To find where the rotation happened (the smallest item), compare items[mid] with items[high]. If items[mid] > items[high], the drop is to the right of mid, so low = mid + 1. Otherwise the smallest item is at mid or to its left, so high = mid. Loop while low < high and return low.

When values repeat

With repeats, the test can't decide. In [2, 2, 2, 0, 2], items[low], items[mid], and items[high] are all 2, so you can't tell which half is sorted. The usual fix is to shrink both ends by one (low++ and high--) and try again. That still works, but in the worst case every item is checked, so it becomes O(n).

Work it by hand

Every step in a table, with why

Look for 26 in a list that was sorted from 4 to 33 and then rotated. It isn't there, so the trace shows each kind of step until the range is empty.

items = [24, 29, 33, 4, 9, 13, 17, 20], target = 26

Steplowhighmiditems[mid]Sorted halfWhat happensWhy
10734right: 4 to 2026 not in 4..20, so high = 2items[0] = 24 is bigger than items[3] = 4, so the drop is on the left and the right half is sorted. 26 is bigger than 20, so it can't be there.
202129left: 24 to 2924 <= 26 < 29, so high = 0Now 24 <= 29, so the left half is sorted, and 26 fits between its ends. Keep the left.
300024left: just 2426 < 24 is false, so low = 1One item is left and low === mid. The one-item left half counts as sorted, which is why the test uses <=. 26 doesn't fit in it.
410---low > high: stopThe range is empty, so 26 is not in the list.

It returns -1 after 3 checks. A linear scan would have read all 8 items to be sure.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Binary search in a rotated listO(log n)O(1)The values are distinct and you search the rotated list as it is, in one pass.
Find the rotation point, then binary searchO(log n)O(1)You also need the rotation point itself, or you prefer two simple searches to one tricky one.
Linear searchO(n)O(1)The list is small, or values repeat so much that the fast version loses its speed anyway.

Extra memory: O(1): low, high, and mid.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Binary search in a rotated list and the other approaches, on a scale where each line up is 10 times more steps.
  • Binary search in a rotated list, Find the rotation point, then binary search O(log n)
  • Linear search O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Binary search in a rotated list31020
Find the rotation point, then binary search31020
Linear search101,0001 million

Inputs that need care

5 tricky inputs
No rotation at all: [4, 9, 13, 17, 20, 24, 29, 33]
items[low] <= items[mid] is always true, so the left half always looks sorted and the loop behaves exactly like plain binary search. Searching for 29 returns 6.
Two items with the drop between them: [9, 4], target 4
mid is 0, so the left half is just [9] and counts as sorted. 4 isn't in it, so low = 1, and the next check finds 4 at index 1. With < instead of <= in the half test, this input returns -1.
One item: [7]
low, mid, and high are all 0. It returns 0 if 7 is the target. Otherwise the range becomes empty and it returns -1.
An empty list: []
high starts at -1, so the loop never runs and it returns -1.
Repeated values: [2, 0, 2, 2, 2], target 0
This code returns -1, which is wrong. Before the half test, add: if items[low], items[mid], and items[high] are all equal, do low++ and high-- and loop again. Both dropped items equal items[mid], which was already checked, so neither can be the target.

Variations and follow-ups

Twists interviewers add

Find the smallest item

Compare items[mid] with items[high]: if it is bigger, the drop is to the right of mid, so low = mid + 1; otherwise high = mid. Loop while low < high. The result is the rotation point, 3 in the trace's list, which also tells you how far the list was rotated.

Two-step search

Find the rotation point p first, then binary search 0 to p - 1 if target >= items[0], or p to n - 1 otherwise. Both steps are O(log n). It is longer, but each part is a standard search, which some people find easier to get right under pressure.

Known rotation amount

If you already know where the list starts, like the head index k of a ring buffer, skip the half tests. Binary search plain positions 0 to n - 1 and read items[(i + k) % n]. The list then looks sorted to the search.

Repeated values

Shrinking both ends when the low, middle, and high items are equal keeps the answer correct but makes the worst case O(n), for lists like [1, 1, 1, 1, 0, 1, 1]. No method can do better in general, because one odd item hidden among copies can only be found by looking at each spot.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "sorted array rotated at an unknown point", "circular", "wraps around", or a sorted list that "starts in the middle", together with a request for O(log n).
  • Explain it out loud: "one half is always sorted; I check whether the target fits between that half's ends; if it does I keep it, otherwise I keep the other half". Drawing the list as two rising lines with a drop makes this easy to follow.
  • Test by hand: no rotation, a two-item list with the drop between, the target at the drop (the smallest item), and a missing target. The two-item case catches < versus <= in the half test.
  • The usual follow-up is "what if there are duplicates?". Answer: when the low, middle, and high items are equal you can't tell which half is sorted, so shrink both ends by one. The worst case becomes O(n), and no algorithm can beat that in general.

Where frontend code uses it

The same idea in real UI code
  • A fixed-size circular log, such as an in-app event recorder that keeps the last 500 events and overwrites the oldest one, stores sorted timestamps that wrap around. Searching it by time is a rotated binary search.
  • A carousel or a list of time-zone offsets can start from any position while the values still wrap around in order.
  • Finding the newest entry in a ring buffer without a saved head pointer is the "find the smallest" form of this search.

Related algorithms