Skip to content
ReadMe Daily

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

Rotated Sorted Arrays

How to binary search a sorted array that has been rotated: spot the single drop, find the smallest item in O(log n), and cope when duplicates hide the drop.

A rotated sorted array is a sorted array whose front part has been cut off and stuck on the end. It is no longer sorted, but it is so nearly sorted that binary search still works on it, with one extra comparison per step.

The idea

Picture a row of numbered library books, in order, on one shelf. Someone lifts the first few off the left end and pushes them back in at the right end. The numbers now climb, fall once, and climb again:

sorted:    [10, 20, 30, 40, 50, 60, 70]
rotated:   [40, 50, 60, 70, 10, 20, 30]
            └── climbing ──┘ └ climbing ┘
                          ↑
                     the one drop

Three facts follow from that picture, and every problem in this family is solved with them.

  1. There is at most one drop. A drop is a place where an item is larger than the one after it. A sorted array has none. Rotating it creates exactly one, where the old end meets the old start. If you also compare the last item with the first, as if the array were a ring, a rotated sorted array has at most one drop in the whole ring.
  2. The smallest item sits just after the drop. Its index is also the number of places the array was rotated by. This index is called the rotation point.
  3. Cut the array anywhere and one of the two pieces has no drop in it. There is only one drop to go round, so it cannot be in both pieces. A piece with no drop is an ordinary sorted array.

When to use it

  • The input is described as sorted and then rotated, shifted or "cycled" by an unknown amount.
  • You are asked for the smallest item, the rotation count, or the position of a target, in O(log n) time.
  • The values climb, fall once, and climb again. (If they climb and then only fall, that is a mountain, covered in peak finding.)

Fact 1 in code: counting drops

Counting drops is the test for whether an array is a rotated sorted array at all. The % numbers.length makes the last item compare with the first.

function countDrops(numbers) {
  let drops = 0;
  for (let i = 0; i < numbers.length; i++) {
    const next = numbers[(i + 1) % numbers.length];
    if (numbers[i] > next) drops++;
  }
  return drops;
}
 
console.log(countDrops([40, 50, 60, 70, 10, 20, 30])); // 1
console.log(countDrops([10, 20, 30, 40]));             // 1
console.log(countDrops([10, 10, 10]));                 // 0
console.log(countDrops([30, 10, 40, 20]));             // 2

A sorted array with at least two different values scores 1, not 0: the wrap-around from its largest item back to its smallest is its one drop. Only an array of identical values scores 0. Anything scoring 2 or more is not a rotated sorted array. This is a single pass, so it takes O(n) time; see Check if Array Is Sorted and Rotated.

Fact 2 in code: finding the rotation point

Looking for the drop item by item takes O(n). Binary search finds it in O(log n) by asking one question about the middle item: is it larger than the item at the right end?

  • Yes. Values only climb inside a sorted run, so a middle that is larger than the right end must be in the first run. The drop, and the smallest item, are somewhere to the right of the middle.
  • No. The stretch from the middle to the right end has no drop in it. The smallest item is the middle itself or something to its left.
// Index of the smallest item. All values must be different.
function rotationPoint(numbers) {
  let lo = 0;
  let hi = numbers.length - 1;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (numbers[mid] > numbers[hi]) {
      lo = mid + 1;   // the drop is to the right of mid
    } else {
      hi = mid;       // mid may be the smallest, so keep it
    }
  }
  return lo;
}
 
console.log(rotationPoint([40, 50, 60, 70, 10, 20, 30])); // 4
console.log(rotationPoint([10, 20, 30, 40]));             // 0

This is the lower-bound shape from the binary search page: lo < hi, hi = mid, and the two bounds close in on a single index.

Walkthrough

rotationPoint([40, 50, 60, 70, 10, 20, 30]):

lo hi mid (value) Right end Larger than the right end? Action
0 6 3 (70) 30 Yes lo = 4
4 6 5 (20) 30 No hi = 5
4 5 4 (10) 20 No hi = 4
4 4 lo and hi have met Return 4

Three looks at seven items. The smallest value is numbers[4], which is 10, and the array was rotated by four places.

Why the right end and not the left

Comparing the middle with the left end looks just as natural, but it cannot tell two cases apart. Take a middle value that is larger than the left end:

[10, 20, 30, 40, 50]   middle 30 > left 10, smallest is on the LEFT
[30, 40, 50, 10, 20]   middle 50 > left 30, smallest is on the RIGHT

The same answer to the question leads to opposite sides, so an array that was never rotated needs a special case. The right-end comparison has no such gap: in the first array 30 is not larger than 50, so the search goes left; in the second 50 is larger than 20, so it goes right.

Fact 3 in code: searching for a target

To find a particular value, use the third fact. At each step, work out which piece beside the middle is in order, then check whether the target lies between the two ends of that piece. If it does, search there. If it does not, the target can only be in the other piece.

Check What it tells you
Left end ≤ middle The left piece has no drop: it is sorted
Otherwise The right piece has no drop: it is sorted
Target between the ends of the sorted piece Search that piece
Target outside them Search the other piece

Search in Rotated Sorted Array builds this step by step for arrays of distinct values. The version below is the same search, extended to cope with repeated values.

When duplicates break the guarantee

All of the reasoning so far leans on a comparison having a clear answer. Repeated values take that away. Suppose the left end, the middle and the right end are all 5:

[5, 5, 5, 5, 5, 2, 5]   smallest is right of the middle
[5, 2, 5, 5, 5, 5, 5]   smallest is left of the middle
 ↑        ↑        ↑
 lo      mid       hi   all three are 5 in both arrays

The three values the search has looked at are identical in both arrays, so no rule based on them can pick the correct side for both. The honest response is to stop halving for one step and shrink the range by a single item instead.

When looking for the smallest item, that means: if the middle equals the right end, drop the right end. Nothing is lost, because the middle holds the same value and stays in the range.

// Smallest value. Repeated values are allowed.
function smallestWithDuplicates(numbers) {
  let lo = 0;
  let hi = numbers.length - 1;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (numbers[mid] > numbers[hi]) {
      lo = mid + 1;
    } else if (numbers[mid] < numbers[hi]) {
      hi = mid;
    } else {
      hi--;           // equal: cannot tell, so give up one item
    }
  }
  return numbers[lo];
}
 
console.log(smallestWithDuplicates([5, 5, 5, 5, 5, 2, 5])); // 2
console.log(smallestWithDuplicates([5, 2, 5, 5, 5, 5, 5])); // 2

When looking for a target, the unclear case is the one where both ends equal the middle. Neither end is the target (the middle has just been checked and it was not), so both can go.

// Is target in the rotated array? Repeated values are allowed.
function rotatedHasValue(numbers, target) {
  let lo = 0;
  let hi = numbers.length - 1;
 
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (numbers[mid] === target) return true;
 
    if (numbers[lo] === numbers[mid] && numbers[mid] === numbers[hi]) {
      lo++;           // cannot tell which piece is sorted
      hi--;
    } else if (numbers[lo] <= numbers[mid]) {
      // The left piece, lo..mid, is sorted.
      if (numbers[lo] <= target && target < numbers[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // The right piece, mid..hi, is sorted.
      if (numbers[mid] < target && target <= numbers[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return false;
}
 
console.log(rotatedHasValue([5, 5, 5, 5, 5, 2, 5], 2)); // true
console.log(rotatedHasValue([5, 2, 5, 5, 5, 5, 5], 3)); // false

The price is speed. On an array that is almost all one value, the search may shrink by one item per step all the way down, which is O(n). That is not a weakness of this code: with the two arrays above, any method has to look at nearly every position before it can rule out a hidden 2.

Variations

Question Comparison to make Example
Is this a rotated sorted array? Each item with the next, wrapping round Check if Array Is Sorted and Rotated
Smallest item, distinct values Middle with the right end Find Minimum in Rotated Sorted Array
Smallest item, duplicates allowed Middle with the right end; on a tie, drop the right end Find Minimum in Rotated Sorted Array II
Position of a target Left end with the middle, then a range check Search in Rotated Sorted Array

Complexity

  • Distinct values: O(log n) time. Every step discards half of the range, exactly as in plain binary search.
  • Duplicates allowed: O(n) time in the worst case, O(log n) when ties are rare. Each tie removes only one or two items.
  • Counting drops: O(n) time. Every neighbouring pair has to be compared once.
  • Space: O(1) for all of them. Only the two bounds and the midpoint are stored.

If these terms are new, Big O notation explained covers them.

Common mistakes

  • Running plain binary search. Comparing the target with the middle alone sends the search the wrong way across the drop.
  • Comparing the middle with the left end to find the smallest item. It gives the same answer for an unrotated array and a rotated one, as shown above.
  • Writing hi = mid - 1 when the middle is not larger than the right end. The middle might be the smallest item; throwing it away loses the answer.
  • Forgetting the wrap-around when counting drops. [20, 10, 30, 40] has one drop inside it, but 40 back to 20 is a second, so it is not a rotated sorted array.
  • Using the distinct-values code on data with duplicates. A tie between the middle and the right end is treated as "go left", and the smallest item can be left behind on the right.
  • Shrinking the left end on a tie when finding the smallest item. The left end may be the only copy of the smallest value in an unrotated range such as [1, 3, 3]. Shrink the right end.

Practise

  1. Check if Array Is Sorted and Rotated (easy): counting drops, including the wrap-around.
  2. Find Minimum in Rotated Sorted Array (medium): comparing the middle with the right end.
  3. Search in Rotated Sorted Array (medium): finding the piece that is in order.
  4. Find Minimum in Rotated Sorted Array II (hard): what to do when duplicates hide the drop.

Practice problems

ProblemDifficultyTimeSpaceRead
Check if Array Is Sorted and RotatedeasyO(n)O(1)Medium read: 8 min
Find Minimum in Rotated Sorted ArraymediumO(log n)O(1)Medium read: 8 min
Find Minimum in Rotated Sorted Array IIhardO(log n) typical, O(n) worst caseO(1)Long read: 9 min