Search in a rotated sorted array

Prerequisites

• Binary search, which this modifies.
• Rotation: moving the first $k$ elements to the end, e.g. [0, 1, 2, 4, 5, 6, 7] → [4, 5, 6, 7, 0, 1, 2].
• Checking whether a value lies in a range: $a \le x < b$.

The analogy

How it works

Data requirement: a sorted array that has been rotated, with distinct values.

Start with one search by hand

Look for 0 in [4, 5, 6, 7, 0, 1, 2], indices 0 to 6. Guess first, then open "Check".

Finish the picture

Search the same array for 5.

• Step 1. Middle 7, and the left half 4..7 is sorted. Predict: is 5 in it?
  Check

  Yes, 4 ≤ 5 < 7, so keep the left side, indices 0..2.

• Step 2. The middle of 0..2 is index 1. Predict the result.
  Check

  a[1] = 5: found in 2 probes.

The rule in plain words

Look at the middle. If it's the target, done. Otherwise decide which half is sorted by comparing a[lo] with a[mid].

If the target fits between the ends of that sorted half, search there. If not, search the other half.

The code

Read this code after you have done one search by hand. It will make more sense.

int search_rotated(const int a[], int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[lo] <= a[mid]) {                        /* left half is sorted */
            if (a[lo] <= x && x < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                      /* right half is sorted */
            if (a[mid] < x && x <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

flowchart TD
  A["mid = middle of lo..hi"] --> B{"a[mid] == x ?"}
  B -->|yes| C["Return mid"]
  B -->|no| D{"a[lo] <= a[mid] ?"}
  D -->|"yes: left sorted"| E{"a[lo] <= x < a[mid] ?"}
  D -->|"no: right sorted"| F{"a[mid] < x <= a[hi] ?"}
  E -->|yes| G["Go left"]
  E -->|no| H["Go right"]
  F -->|yes| H
  F -->|no| G
          

How fast is it?

Each round halves the range, exactly like binary search, so at most:

With duplicates, such as [2, 2, 2, 3, 2], a[lo] == a[mid] can't tell which half is sorted, and the worst case drops to $O(n)$.

Common mistakes

• Testing the target against the unsorted half, where "between the ends" means nothing.
• Mixing strict and non-strict bounds: the sorted-left test is a[lo] <= x < a[mid], because a[mid] was already checked.
• Promising $O(\log n)$ when duplicates are allowed.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• One half is always sorted because the rotation creates only one "wrap" point, and it can be in only one half.
• We test the target against the sorted half because only there does "between the ends" mean "inside".
• It is $O(\log n)$ with distinct values because each round still throws away half the range.
• Duplicates can make it $O(n)$ because a[lo] == a[mid] no longer reveals which half is sorted.
• Extra space is $O(1)$ because it keeps only lo, hi and mid.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is a rotated array like a clock read from 4 o'clock?
   Sample answer

   It runs in order, wraps around once, then runs in order again. Cut it in two, and at least one half has no wrap, so it's plainly sorted.

2. Walk through a search for 0 in [4, 5, 6, 7, 0, 1, 2].
   Sample answer

   Middle 7: the left half 4..7 is sorted but doesn't hold 0, so go right. Middle 1: the part 0..1 is sorted and holds 0, so go left. a[4] = 0, found.

3. Why does the code compare a[lo] with a[mid]?

   A good answer says what a[lo] ≤ a[mid] proves.

   Sample answer

   If a[lo] ≤ a[mid], there's no wrap between them, so the left half is sorted. Otherwise the wrap is on the left, which means the right half is sorted.

4. So what is rotated array search, in one sentence?
   Sample answer

   It's binary search that finds the sorted half each round and keeps it only if the target lies within it.

5. Why does every round still remove half the range?
   Sample answer

   Each round decides between the left and right of mid, exactly like binary search. Only the way of deciding is different.

6. What are its best, average and worst cases?
   Sample answer

   Best $O(1)$, average and worst $O(\log n)$ with distinct values, but $O(n)$ in the worst case with duplicates. Extra space $O(1)$.

7. Why do duplicates break the $O(\log n)$ guarantee?

   A good answer gives a case where you can't decide.

   Sample answer

   In [2, 2, 2, 3, 2], a[lo], a[mid] and a[hi] are all 2, so you can't tell which half is sorted. You may have to shrink the range one step at a time.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the strict-versus-non-strict bounds and the duplicates case. I'd keep the clock analogy, the search for 0, and "one half is always sorted, so test against it, $O(\log n)$".

External resources

• GeeksforGeeks: Search in a rotated sorted array: two approaches with code.
• LeetCode 33: Search in Rotated Sorted Array: practise the exact problem with test cases.
• Wikipedia: Binary search: the base algorithm and its variations.

Videos

• YouTube search: search in rotated sorted array explained: pick a walkthrough.