SyntaxPilot
Courses/DSA and Coding Problems/Lesson 13

DSA and Coding Problems · Lesson 13 of 90 · 12 min

Search in a rotated sorted array

queued

These are the notes for DSA episode 13, the second episode of the binary search block. The problem is Search in Rotated Sorted Array (LeetCode 33). The array was sorted, then rotated at an unknown point, so it is no longer sorted from left to right. A linear scan per query is O(n) and times out on ten lakh rows and one lakh queries. Last episode's plain binary search gives a wrong answer. The fix is one question asked at every mid: which half is sorted? One half always is, and a sorted half tells you for certain whether the target can be inside it. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A big railway station's timetable for the day is sorted by time: 00:30, 05:40, 09:00, ..., 22:00. But the departure board starts at now. At six in the evening it shows 18:00, 19:30, 22:00, and then wraps around to 00:30, 05:40, ... The list is still sorted, just rotated. A passenger asks: is the 05:40 train on the board, and on which row? Hundreds of passengers ask this all day, for different trains, so each answer must be fast.

Problem statement

An array a of distinct integers was sorted in increasing order and then rotated at an unknown index (the front part moved to the back). Given a target t, return its index, or -1 if it is missing. The solution must run in O(log n) time.

a t answer
[4, 5, 6, 7, 0, 1, 2] 0 4
[4, 5, 6, 7, 0, 1, 2] 3 -1
[4, 5, 6, 7, 0, 1, 2] 4 0 (first element)
[4, 5, 6, 7, 0, 1, 2] 2 6 (last element)
[1, 2, 3, 4, 5] 4 3 (rotated by zero: plain sorted)
[1] 1 / 0 0 / -1
[3, 1] 1 1
[] 7 -1

What "rotated" means. Start from [0, 1, 2, 4, 5, 6, 7], cut it after the 2, and move the front part to the back: [4, 5, 6, 7, 0, 1, 2]. The result is two sorted runs with exactly one drop between them (here 7 → 0). Everything in this episode follows from that picture.

Solution 1: brute force (scan every row)

Walk the array until you find the target.

public class Main {
    static int linear(int[] a, int t) {
        for (int i = 0; i < a.length; i++)
            if (a[i] == t) return i;
        return -1;
    }
    public static void main(String[] args) {
        int[] a = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(linear(a, 0));
        System.out.println(linear(a, 3));
    }
}

Output:

4
-1

Correct. Now the big station: ten lakh entries (rotated) and one lakh questions. We add up the answers so the output stays short.

        int n = 1000000, q = 100000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = (i + 300000) % n * 2;
        long t0 = System.nanoTime(), sum = 0;
        for (int k = 0; k < q; k++)
            sum += linear(a, (int) (k * 7919L % n) * 2);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println(sum + "   " + ms + " ms");

Result: Time Limit Exceeded (the 8-second limit).

The array is "sorted", so try last episode's idea directly:

    static int plain(int[] a, int t) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == t) return mid;
            if (a[mid] < t) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

plain(a, 0) printed -1 and plain(a, 5) printed 1. Wrong answer for 0, which sits at index 4. The middle is 7; since 0 < 7, plain binary search throws away the right half, which is exactly where 0 lives, after the drop.

Why it is slow, and why plain binary search breaks

  • The linear scan costs O(n) per query: 10⁵ queries × 10⁶ rows = 10¹¹ steps.
  • The plain rule "t < a[mid] means t is on the left" is only true when the whole array is sorted. After a rotation, the smallest values sit on the right, so the rule sends you the wrong way.
  • We need a rule that is still true after rotation.

The key insight: cut at mid, one half is always sorted

The array has exactly one drop. Cut it at mid: the drop lands in the left half or the right half, never in both. The half without the drop is perfectly sorted, and one comparison tells you which one it is:

  • a[lo] <= a[mid] → the left half a[lo..mid] is sorted.
  • otherwise → the right half a[mid..hi] is sorted.

A sorted half is easy: its smallest value is at one end and its largest at the other, so t is inside it only if it lies between those two ends. If it does, search that half; if not, search the other half. Either way half the range is thrown away, so it is still O(log n).

if (a[mid] == t) return mid;
if (a[lo] <= a[mid])                 // left half sorted
    a[lo] <= t < a[mid] ? go left : go right
else                                 // right half sorted
    a[mid] < t <= a[hi] ? go right : go left

Note that this time the range is closed, [lo, hi] with hi = n - 1, because the rule reads a[hi], so hi must always be a real index.

Dry run: search([4, 5, 6, 7, 0, 1, 2], 0)

Step lo hi mid a[mid] Sorted half Is 0 inside? Action
1 0 6 3 7 left [4..7] 4 <= 0 < 7? no lo = 4
2 4 6 5 1 left [0..1] 0 <= 0 < 1? yes hi = 4
3 4 4 4 0 found return 4

Three looks, and we never had to find where the drop is.

Solution 2: the optimal solution, typed live

public class Main {
    static int search(int[] a, int t) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == t) return mid;
            if (a[lo] <= a[mid]) {
                if (a[lo] <= t && t < a[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (a[mid] < t && t <= a[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] a = {4, 5, 6, 7, 0, 1, 2};
        System.out.println(search(a, 0));
        System.out.println(search(a, 3));
        System.out.println(search(a, 4));
        System.out.println(search(a, 2));
        System.out.println(search(new int[]{1, 2, 3, 4, 5}, 4));
        System.out.println(search(new int[]{1}, 1));
        System.out.println(search(new int[]{1}, 0));
        System.out.println(search(new int[]{3, 1}, 1));
        System.out.println(search(new int[0], 7));
    }
}

Output:

4
-1
0
6
3
0
-1
1
-1

All nine are correct: both examples, the first and last element, an array rotated by zero, a single element (found and missing), two elements, and an empty array (hi = -1, so the loop never runs).

The same big input that timed out (ten lakh rows, one lakh questions) printed:

49997050000   32 ms

The same total the scan would produce, in milliseconds: about 20 looks per question instead of up to ten lakh.

The same solution in C++ and Python

#include <bits/stdc++.h>
using namespace std;

int search(const vector<int>& a, int t) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == t) return mid;
        if (a[lo] <= a[mid]) {                    // left half is sorted
            if (a[lo] <= t && t < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                  // right half is sorted
            if (a[mid] < t && t <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int main() {
    vector<int> a = {4, 5, 6, 7, 0, 1, 2};
    cout << search(a, 0) << " " << search(a, 3) << " " << search(a, 4) << " " << search(a, 2) << "\n";
    cout << search({1, 2, 3, 4, 5}, 4) << " " << search({1}, 1) << " " << search({1}, 0) << " "
         << search({3, 1}, 1) << " " << search({}, 7) << "\n";
}
def search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2          # Python ints never overflow
        if a[mid] == t:
            return mid
        if a[lo] <= a[mid]:           # left half is sorted
            if a[lo] <= t < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                         # right half is sorted
            if a[mid] < t <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

a = [4, 5, 6, 7, 0, 1, 2]
print(search(a, 0), search(a, 3), search(a, 4), search(a, 2))
print(search([1, 2, 3, 4, 5], 4), search([1], 1), search([1], 0), search([3, 1], 1), search([], 7))

Both print:

4 -1 0 6
3 0 -1 1 -1

The classic bug: < instead of <=

Many people write the sorted-half test as a[lo] < a[mid]:

            if (a[lo] < a[mid]) {

search(new int[]{3, 1}, 1) printed -1 (wrong: 1 is at index 1) while search(new int[]{3, 1}, 3) printed 0, so a quick test would miss it. With two elements, mid == lo, so a[lo] == a[mid]. The strict test says "left half not sorted", we take the right-half branch, a[mid] < t is 3 < 1, false, so hi = mid - 1 and we miss the 1. A half with one element is always sorted, so the test must be <=.

Two follow-ups interviewers ask

1. Find the minimum (the rotation point). Compare a[mid] with a[hi]: if a[mid] > a[hi] the drop is to the right of mid, so lo = mid + 1; otherwise mid could be the minimum, so hi = mid. This is last episode's template (half-open style shrinking), and it ends on the minimum.

    static int findMin(int[] a) {
        int lo = 0, hi = a.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] > a[hi]) lo = mid + 1;
            else hi = mid;
        }
        return a[lo];
    }

findMin({4, 5, 6, 7, 0, 1, 2}) printed 0, findMin({11, 13, 15, 17}) printed 11.

2. Duplicates allowed (LeetCode 81), e.g. [1, 0, 1, 1, 1]. Now a[lo] == a[mid] == a[hi] can happen, and then you cannot tell which half is sorted. The fix is to shrink both ends by one; in the worst case (almost all values equal) that makes it O(n).

    static boolean searchDup(int[] a, int t) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == t) return true;
            if (a[lo] == a[mid] && a[mid] == a[hi]) { lo++; hi--; }
            else if (a[lo] <= a[mid]) {
                if (a[lo] <= t && t < a[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (a[mid] < t && t <= a[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return false;
    }

searchDup({1, 0, 1, 1, 1}, 0) printed true; searchDup({2, 5, 6, 0, 0, 1, 2}, 3) printed false.

Complexity

Approach Time per query Extra space 10⁶ rows, 10⁵ queries
Linear scan O(n) O(1) Time Limit Exceeded
Plain binary search O(log n) O(1) wrong answers
Find the sorted half O(log n) O(1) 32 ms
With duplicates O(log n) usually, O(n) worst O(1)

We never "un-rotate" or copy the array; we only ask a smarter question at mid.

Common mistakes

Mistake What you see Why Fix
Plain binary search on the rotated array plain(a, 0) = -1 (0 is at index 4) t < a[mid] no longer means "left" first find the sorted half
if (a[lo] < a[mid]) search({3, 1}, 1) = -1 when lo == mid, a one-element half is sorted a[lo] <= a[mid]
a[lo] < t && t < a[mid] search(a, 4) = -1 (4 is at index 0) the sorted half includes its first end a[lo] <= t
Half-open hi = a.length, while (lo < hi) search(a, 0) = -1, and search({3, 1}, 2) throws ArrayIndexOutOfBoundsException: Index 2 out of bounds for length 2 the rule reads a[hi] hi = a.length - 1, while (lo <= hi)
(lo + hi) / 2 can overflow for huge ranges (see episode 12) int overflow lo + (hi - lo) / 2

Mini project: the departure board

Store a day's departure times as minutes after midnight (05:40 → 340), sorted, then rotate the array so it starts at the current time. Answer queries "is the train at HH:MM on the board, and on which row?" with search. Extension: use findMin to find the row where the board wraps past midnight, and print the next three departures after a given time.

Practice

  1. Find Minimum in Rotated Sorted Array (LeetCode 153).
Solution

findMin above: compare a[mid] with a[hi]. If a[mid] > a[hi], the minimum is to the right (lo = mid + 1), else hi = mid. O(log n). findMin({4, 5, 6, 7, 0, 1, 2}) = 0.

  1. How many times was a sorted array rotated? ([15, 18, 2, 3, 6, 12] was rotated 2 times.)
Solution

The rotation count equals the index of the minimum. Return lo instead of a[lo] from findMin: for [15, 18, 2, 3, 6, 12] it printed 2.

  1. Search in Rotated Sorted Array II (LeetCode 81, duplicates allowed).
Solution

searchDup above: when a[lo] == a[mid] == a[hi], do lo++; hi--. It printed true for 0 in [1, 0, 1, 1, 1].

  1. Why does [1, 0, 1, 1, 1] force O(n) in the worst case?
Solution

At the first mid, a[lo] = a[mid] = a[hi] = 1. Both [1, 0, 1] and [1, 1, 1] patterns are possible for the halves, so no comparison can tell which half holds the 0. You can only discard the two ends; with many equal values that is one step at a time.

Quick quiz

What does search(new int[]{30, 40, 50, 10, 20}, 10) return?

  • 3
  • 0
  • -1
  • 4
Answer

3. mid = 2, a[2] = 50. a[lo] = 30 <= 50, so the left half [30..50] is sorted, but 10 is not in it → lo = 3. Next mid = 3, a[3] = 10: found at index 3.

Interview questions

  1. Why is one half always sorted? A rotated sorted array has exactly one drop. Cutting at mid puts the drop in at most one half; the other has none, so it is sorted.
  2. How do you know which half is sorted? a[lo] <= a[mid] means the left half is sorted; otherwise the right half is.
  3. Why <= and not <? When lo == mid the left half is a single element, which is sorted; < would wrongly send you to the right-half branch.
  4. Can you find the rotation point first and then binary search one side? Yes: findMin gives the pivot in O(log n), then a normal binary search on the correct side. Same complexity, two passes.
  5. What changes with duplicates? a[lo] == a[mid] == a[hi] gives no information; shrink both ends. Worst case becomes O(n).
  6. Time and space? O(log n) time, O(1) space.

Glossary

Term Meaning
Sorted array Each element is <= the next one
Rotation Cutting a sorted array at some index and moving the front part to the back: [0..7] → [4, 5, 6, 7, 0, 1, 2]
Pivot / rotation point The index where the drop happens; it holds the minimum
Sorted run A stretch of the array that is in increasing order
Drop The one place where a value is followed by a smaller value (7 → 0)
Distinct values No value appears twice
Linear scan Checking elements one by one: O(n)
Binary search Checking the middle of a range and discarding the half that can't hold the answer: O(log n)
Closed range [lo, hi] Both ends are real indexes that may still hold the answer
lo, hi, mid The ends of the range still being searched, and its middle index
Wrong Answer The program runs without crashing but prints an incorrect result
Time Limit Exceeded (TLE) The program is too slow for the judge's limit (8 s in the SyntaxPilot compiler)
ArrayIndexOutOfBoundsException Java's runtime error for reading an index outside 0..length-1
O(log n) Work that grows with the number of halvings: about 20 steps for 10⁶

Summary

  • A rotated sorted array is two sorted runs with one drop.
  • A linear scan is O(n) per query: Time Limit Exceeded on 10⁶ rows × 10⁵ queries.
  • Plain binary search gives a wrong answer: t < a[mid] no longer means "left".
  • Cut at mid: one half is always sorted. Find it with a[lo] <= a[mid], check t against that half's two ends, discard the other half.
  • Use <= (a one-element half is sorted), a closed range [0, n - 1], and lo + (hi - lo) / 2.
  • O(log n) time, O(1) space; with duplicates, O(n) in the worst case.

Next episode: Binary search on the answer: Koko eating bananas, aggressive cows.