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 dropThree facts follow from that picture, and every problem in this family is solved with them.
- 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.
- 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.
- 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])); // 2A 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])); // 0This 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 RIGHTThe 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 arraysThe 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])); // 2When 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)); // falseThe 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 - 1when 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
- Check if Array Is Sorted and Rotated (easy): counting drops, including the wrap-around.
- Find Minimum in Rotated Sorted Array (medium): comparing the middle with the right end.
- Search in Rotated Sorted Array (medium): finding the piece that is in order.
- Find Minimum in Rotated Sorted Array II (hard): what to do when duplicates hide the drop.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Check if Array Is Sorted and Rotated | easy | O(n) | O(1) | Medium read: 8 min |
| Find Minimum in Rotated Sorted Array | medium | O(log n) | O(1) | Medium read: 8 min |
| Find Minimum in Rotated Sorted Array II | hard | O(log n) typical, O(n) worst case | O(1) | Long read: 9 min |