Skip to content
ReadMe Daily

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

Search in Rotated Sorted Array

Find a target in a sorted array that has been rotated, still in O(log n), by working out which half around the middle is in order at each step.

mediumPattern: Binary Search

Updated Medium read: 6 min read

Approaches at a glance

ApproachTimeSpace
Linear scanO(n)O(1)
Binary search on the ordered halfO(log n)O(1)

The problem

An array of distinct integers was sorted in ascending order and then rotated: some number of elements were taken off the front and put on the end. [0, 1, 2, 4, 5, 6, 7] rotated by four places becomes [4, 5, 6, 7, 0, 1, 2]. You are not told how far it was rotated, and it may not have been rotated at all.

Given such an array and a target, return the index of the target, or -1 if it is absent. The solution must run in O(log n) time.

numbers = [4, 5, 6, 7, 0, 1, 2], target = 0   →  4
numbers = [4, 5, 6, 7, 0, 1, 2], target = 3   →  -1
numbers = [1],                   target = 0   →  -1

Approach 1: linear scan

Ignore the ordering and look at every element.

JavaScript

function searchRotatedLinear(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    if (numbers[i] === target) return i;
  }
  return -1;
}

Python

def search_rotated_linear(numbers, target):
    for i, value in enumerate(numbers):
        if value == target:
            return i
    return -1

Time O(n), space O(1). It is correct, but it does not meet the O(log n) requirement and makes no use of what is known about the array.

What rotation does to the array

A rotated sorted array is two sorted runs placed end to end, where everything in the first run is larger than everything in the second:

[4, 5, 6, 7,   0, 1, 2]
 └ ascending ┘ └ ascending ┘

There is a single drop, here from 7 to 0. Ordinary binary search fails because comparing the target with the middle element no longer says which side the target is on: with the middle at 7 and a target of 0, the target is smaller yet lies to the right.

The observation that rescues it: cut the range anywhere, and at least one of the two halves contains no drop, because there is only one drop to go round. A half with no drop is plainly sorted, and for a sorted half a range check is all it takes to know whether the target is inside.

Approach 2: binary search on the ordered half

At each step:

  1. Look at the middle element. If it is the target, stop.
  2. Decide which half is in order. If numbers[lo] <= numbers[mid], the left half is; otherwise the right half is.
  3. Check whether the target lies between the two ends of that ordered half. If it does, search there. If not, it can only be in the other half.

JavaScript

function searchRotated(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 mid;
 
    if (numbers[lo] <= numbers[mid]) {
      // The left half, lo..mid, is in order.
      if (numbers[lo] <= target && target < numbers[mid]) {
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    } else {
      // The right half, mid..hi, is in order.
      if (numbers[mid] < target && target <= numbers[hi]) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
  }
  return -1;
}

Python

def search_rotated(numbers, target):
    lo = 0
    hi = len(numbers) - 1
 
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if numbers[mid] == target:
            return mid
 
        if numbers[lo] <= numbers[mid]:
            # The left half, lo..mid, is in order.
            if numbers[lo] <= target < numbers[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # The right half, mid..hi, is in order.
            if numbers[mid] < target <= numbers[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

The loop is the exact-value template from the binary search pattern. Only the decision about which way to go has changed.

Walkthrough

numbers = [4, 5, 6, 7, 0, 1, 2], target = 0:

lo hi mid (value) Ordered half Target inside it? Action
0 6 3 (7) Left: 4 to 7 No, 0 is below 4 lo = 4
4 6 5 (1) Left: 0 to 1 Yes, 0 is from 0 up to but not including 1 hi = 4
4 4 4 (0) Found: return 4

And for target = 3, which is absent:

lo hi mid (value) Ordered half Target inside it? Action
0 6 3 (7) Left: 4 to 7 No lo = 4
4 6 5 (1) Left: 0 to 1 No lo = 6
6 6 6 (2) Left: 2 to 2 No lo = 7; range empty, return -1

Time O(log n): the range halves on every step. Space O(1).

Why the comparison is <=, not <

When the range is down to one or two elements, mid equals lo. The "left half" is then the single element at lo, which is trivially in order, and numbers[lo] <= numbers[mid] says so. With a strict <, the code would wrongly decide the right half is the ordered one.

[3, 1] with target 1 shows the difference. lo = 0, hi = 1, mid = 0. With <=, the left half [3] is ordered, 1 is not in it, so the search moves right and finds the target. With <, the code would treat [3, 1] as the ordered half, conclude that 1 is not between 3 and 1, move left and return -1.

The same idea, other questions

  • Find the smallest element of a rotated array (LeetCode 153): compare the middle with the right end to learn which side the drop is on.
  • Duplicates allowed (LeetCode 81): when the left, middle and right values are all equal, there is no way to tell which half is ordered. The only safe move is to shrink the range by one from each end, which makes the worst case O(n).

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1

Python

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1

The comment after each line is the result you should see.

Common mistakes

  • Comparing the target only with the middle. That is ordinary binary search, and it goes the wrong way across the drop.
  • Using < when testing for the ordered half. It fails on two-element ranges, as shown above.
  • Getting the range check's ends wrong. The middle has already been ruled out, so it is excluded (target < numbers[mid]), while the far end is included (numbers[lo] <= target).
  • Finding the drop first, then searching. Locating the rotation point and running a second binary search works, but it is two searches and twice the opportunity for off-by-one errors.

Original problem: LeetCode 33: Search in Rotated Sorted Array