Search in a rotated sorted array

Why it matters

Searching in a rotated sorted array is one of the most asked binary search questions in technical interviews. It looks like a plain binary search problem, and a plain binary search fails on it. Solving it means understanding why binary search works, not just memorising the loop. That is why interviewers use it to separate candidates who know the template from candidates who can adapt it.

By the end of this lesson you will explain what a rotated array is, find the rule that keeps binary search valid, write the search and the minimum-finding function in C++, handle duplicates, and check your code against a brute-force program that tests every case.

The problem

Start with a sorted array of distinct numbers: 0 1 2 4 5 6 7. Now take the front part and move it to the back. Move 0 1 2 to the end, and you get 4 5 6 7 0 1 2. That is a rotated sorted array. It is still in two sorted runs: 4 5 6 7 and 0 1 2. The place where the run changes, between 7 and 0, is the rotation point.

The task is this. Given a rotated sorted array and a target, return the index of the target, or -1 if it is not there. The array has distinct values, and you must answer in O(log n) time. A straight scan would take O(n) and would not satisfy the requirement.

A plain binary search tries to use the order of the whole array. Here the whole array is not in order. If the middle value is 7 and the target is 0, the plain rule says "the target is smaller than the middle, so search left". That is wrong, because 0 is on the right side of the rotation. The plain rule fails. You need one more fact.

The key fact: one half is always sorted

Take any range of a rotated sorted array and cut it at its middle. At least one of the two halves is sorted. You can see this in the picture. The rotation point is a single break in the sequence. It can lie in one half only, or exactly at the middle. In either case, the other half does not contain the break, so it is a normal sorted run.

A rotated sorted array with the sorted half highlighted at each step of the search

This fact is what makes the search possible. Once you know which half is sorted, you can check whether the target lies inside that sorted half by comparing it with the two ends of that half. If it does, search that half. If it does not, the target must be in the other half, which may contain the break, and you search that one instead. Either way, half of the range is thrown away.

Here is the decision in words. Look at the middle value a[mid].

• If a[lo] is less than or equal to a[mid], the left half lo to mid is sorted. If the target is in the range from a[lo] up to but not including a[mid], search left. Otherwise search right.
• Otherwise the right half mid to hi is sorted. If the target is in the range from a[mid] (not including it) up to a[hi], search right. Otherwise search left.

The phrase "in the range" means the target is at least the smallest value of the sorted half and at most the largest value of that half. For the left half that is a[lo] to a[mid], and since a[mid] was already checked, the test stops before it.

Tracing the rule by hand

Trace the search for target 0 in 4 5 6 7 0 1 2. Keep a table with lo, hi, mid, the value at mid, which half is sorted, and what you decide.

At step 1 the left half 4 5 6 7 is sorted, and the target 0 is not inside it, so the search moves right and the break is now in the new range. At step 2 the range 0 1 is sorted, and 0 is inside it. The search moves left. The third step finds the value. Notice that the rotation point was in the range the whole time, and the rule still found the target.

Now trace target 3, which is not in the array. Step 1 is the same: the left half is sorted and 3 is not in 4 5 6 7, so lo becomes 4. Step 2 gives lo = 4, hi = 6, mid = 5, a[mid] = 1. The left half 0 1 is sorted, and 3 is not between 0 and 1, so the search moves right and lo becomes 6. Step 3 has lo = 6, hi = 6, mid = 6, a[mid] = 2. The left half is the single value 2, and 3 is not in it, so lo becomes 7. The range is empty and the answer is -1.

The search in C++

The next program implements the rule. It reads a count, the rotated array, and the target, and prints the index of the target, or -1.

Type this in the Input box, and press Run:

7
4 5 6 7 0 1 2
0

The output is 4. Change the last line to 3 and the output is -1. Try 5 and the output is 1, which is the index of 5 in the array as typed.

Look at the test a[lo] <= a[mid]. It uses <=, not <. The difference matters when the range has one or two values, because then lo and mid can be the same index. If the test were a[lo] < a[mid], a range of one value would take the wrong branch. The common mistakes section shows the exact input that breaks.

The loop uses the inclusive form lo <= hi with hi = mid - 1 and lo = mid + 1, the same template as the previous lesson. You already checked mid against the target, so you can drop it from the next range, and the range always shrinks.

Finding the rotation point

The next question is useful in its own right. Where does the rotation happen? The index of the smallest value is that point. If the array is not rotated at all, the smallest value is at index 0. The number of places the array was rotated left is also the index of the smallest value, which is why interviewers often ask for the rotation count.

The key idea is to compare the middle value with the last value. If a[mid] is bigger than a[hi], the drop from big to small happens to the right of mid, so the minimum is somewhere after mid. Otherwise a[mid] is smaller than or equal to a[hi], which means the right part from mid to hi is sorted, and the minimum is at mid or to its left.

The loop here is different from the search loop. It uses lo < hi and hi = mid, not hi = mid - 1. The reason is that mid may be the answer. The loop keeps the range that certainly contains the minimum, and it stops when that range has one index.

Type 7 and then 4 5 6 7 0 1 2 in the Input box. The output is:

minimum 0 at index 4

Trace it. The range starts as 0..6 with a[hi] = 2. The middle is 3, and a[3] = 7 is bigger than 2, so the minimum is to the right, and lo becomes 4. The range 4..6 has middle 5, with a[5] = 1. Since 1 is not bigger than 2, the minimum is at 5 or to its left, so hi becomes 5. The range 4..5 has middle 4, with a[4] = 0. Since 0 is not bigger than 1, hi becomes 4. Now lo and hi are both 4, so the loop stops. The answer is index 4.

Try an input that was never rotated, such as 5 and 1 2 3 4 5. The output is minimum 1 at index 0. The loop never moves lo in that case, because every middle value is smaller than the last value.

With the rotation point in hand, you can search any rotated array in another way. Find the minimum, then do an ordinary binary search on the logical sorted order. The exercise at the end of this lesson asks you to build that second method.

The same question with duplicates

Duplicates break the rule that one half is always sorted. Consider 1 1 1 1 1 0 1 1. The middle value is 1, the left end is 1, and the right end is 1. You cannot tell whether the left or the right half is sorted, because the drop from 1 to 0 might be on either side. In that case the safe move is to remove one value from each end. The target cannot be lost by doing so, because the two removed values are copies of the middle value, and the middle value was already checked.

The next program handles duplicates. It reads the array and the target and prints whether the target is found. It uses the same rule as before, with one extra branch for the ambiguous case.

Type this in the Input box and press Run:

7
2 5 6 0 0 1 2
0

The output is found. Change the last line to 3 and the output is not found.

The ambiguous case is written as its own branch, before the normal tests. It runs only when all three values are the same: the two ends and the middle. Dropping both ends is safe, because a value equal to the middle has already been compared with the target. Then the loop goes on with a smaller range, and it still checks every possible position.

The cost is the important point. With no duplicates the search is O(log n). With duplicates, the ambiguous case can remove only two values per step. Consider an array of 1000 ones with a single zero placed in the middle of the rotation. Every middle value is a 1, and every end is a 1, so the ambiguous branch fires again and again, and the search can take about 500 steps. The worst case is O(n), not O(log n). Interviewers expect you to say this out loud, and to explain that it is the price of duplicates, not a bug.

Checking the logic against brute force

A good way to trust a tricky algorithm is to compare it with a slow method on every small case. The next program checks the search on every rotation of the arrays 0 to n - 1 for every size from 1 to 8. For each array it tests every target from -1 to n, which covers both present and missing values. It compares the answer with a plain linear search.

Press Run. You do not need input. The output is:

checked 276 cases, 0 mismatches

The number 276 is not random. For each size n, there are n rotations and n + 2 targets, which gives n * (n + 2) cases. Adding those for n from 1 to 8 gives 276. The program counts them, and the count matches the formula, which is a good sign that the loop ran as intended.

Brute force is slow on large inputs, but it is perfect for small ones. Small cases catch most off-by-one errors, because the edge cases such as one value, two values and a missing target all appear at small sizes. When a clever algorithm fails, first reproduce the failure with a small input found by such a check.

Complexity

The bounds explain the trade-off. Distinct values let each step make a clear decision, so the search is logarithmic. Duplicates can hide which half holds the break, so a clear decision is not always possible.

Common mistakes

Using a[lo] < a[mid] instead of <=. When the range has one value, lo and mid are the same index, and the test is false even though the left half is sorted. Take the array 2 1 and search for 1. The correct code finds index 1. A version with < and the same rest of the code returns -1, because it sends the search to the wrong half. This exact example is in the practice exercises.

Leaving out the first value of the sorted half. For the left half, the target must satisfy a[lo] <= target, with the equals sign, because the target can be the very first value. Writing a[lo] < target skips it. Take 4 5 6 7 0 1 2 and search for 4. The first step sees a[lo] equal to 4, so the wrong test is false, the search moves right, and the program returns -1, although 4 is at index 0.

Mixing the two loop templates. The search uses lo <= hi with mid - 1 and mid + 1. The minimum finder uses lo < hi with hi = mid. Copying one loop's updates into the other causes an infinite loop or a skipped answer. Pick a template for each problem and keep it.

Forgetting the duplicate case. The code that works for distinct values can return not found when the array has duplicates. Read the problem statement for the words "distinct" and "unique" before you write code.

Assuming the answer must be at a fixed place. The minimum can be at index 0 when the array is not rotated, and at the last index when only one value is out of place. Test those cases, and do not assume the rotation is always in the middle.

Debugging a rotated search

When a search returns the wrong index, print the state at each step: lo, hi, mid, the value at mid, and which half you decided was sorted. Then compare the printed decisions with the trace you wrote on paper. Most bugs show up at the first wrong decision.

For example, put the buggy < test in place of <= and search for 1 in 2 1. The first step has lo = 0, hi = 1 and mid = 0, with a[mid] = 2. The test a[lo] < a[mid] is 2 < 2, which is false, so the code assumes the right half is sorted. The right half is 2 1, which is not sorted. The target 1 is not inside the assumed range, so hi becomes -1, and the search returns -1. The printed decision shows the right half was assumed sorted, while it was not, and that points straight at the test.

Brute force is also a debugging tool. If the exhaustive check reports a mismatch, print the array and the target that caused it, and trace only that case.

Interview questions and related problems

Interviewers ask this problem in several forms. They may ask you to search, to find the rotation count, to find the minimum with duplicates, or to explain why duplicates change the complexity. A strong answer starts with the key fact, shows the decision rule, handles the edge cases, and states the worst case when duplicates are allowed.

Related problems use the same idea. The peak element problem asks for any value that is bigger than its neighbours, and it uses the slope of the array instead of the sorted halves. Counting values below a target in a rotated array needs the rotation point and then a normal binary search, as the exercises show.

Why the sorted-half rule is correct

Here is a short argument. Start with a sorted array and rotate it once. The values now form two runs. The first run is the top part of the original array, and every value in it is bigger than every value in the second run, which is the bottom part.

Take any range that contains the break, and cut it at its middle. The break is the one place where the value drops. If it lies in the left half, the first value of the left half is bigger than its middle value, because the drop sits between them. In that case the test a[lo] <= a[mid] is false, and the right half holds no drop, so the right half is sorted. If the break lies in the right half, the left half has no drop, and a[lo] <= a[mid] is true. So the test decides correctly which half is sorted.

Once you know a sorted half, the rest is ordinary binary search inside that half. The target can be in the sorted half only if it lies between that half's first and last values. If it does not lie there, it cannot be in the sorted half, so the other half is the only place left. Either way, the step discards a half that cannot contain the target, and the invariant from the binary search lesson still holds.

Walking through the duplicate branch

Trace target 3 in 2 5 6 0 0 1 2 by hand. The table records the state at each step.

The loop ends with the range empty, so the answer is not found. The third row is the duplicate branch in action. It fires on a range of one value, because lo, mid and hi are the same index, so all three values are equal by definition. The branch then moves both ends, and the empty range ends the search. Check this case in your head before you trust the code, because it is the case that a quick test often misses.

Edge cases to test

A single value is a range where lo, mid and hi are the same index. The search compares the value with the target and stops. With distinct values, the sorted-half test is always true here, so the code takes the left branch.

A sorted array is a rotation by 0. The left half is always sorted, and the search becomes an ordinary binary search. Test it, because it proves the rule still works when no rotation happened.

A rotation by one, such as 5 1 2 3 4, puts the smallest value at index 1. Search for 5, the largest value, and then for 1, the smallest value. Both must return the right index.

Targets equal to the first or last value are the cases where a strict comparison fails. The exhaustive check in this lesson covers them, because it tests every target from -1 to n.

Interview follow-ups

Interviewers often ask why duplicates change the complexity, and how you would prove the O(n) worst case. The 1000-value example from this lesson is a good answer. The ambiguous case removes two values per step, and an adversary can place the break so that every step is ambiguous. The search then makes about n / 2 steps, which is linear.

Another follow-up asks for the minimum with duplicates. The loop is the same as before, with one extra branch. When the middle equals the last value, remove the last value, because a copy of it is still in range.

Where rotated arrays appear

Rotated sorted arrays come up in circular buffers. A buffer of fixed size can hold a sorted log of timestamps, after the newest entries wrap around and overwrite the oldest ones. The oldest entry sits at the rotation point, and finding it is the same as finding the minimum. Search in such a buffer needs the same rule, with the sorted halves telling you where to look. The idea also appears in versioned data, where a sorted list is shifted after an update. In each case the rule is identical, and only the storage differs.

Finding the minimum, step by step

Trace the minimum-finding loop on 4 5 6 7 0 1 2. Each row shows the range and what the middle value tells you.

Now lo equals hi, which is 4, and a[4] is 0, the minimum. The loop uses hi = mid, not hi = mid - 1, because mid itself may be the minimum. Throwing mid away would be a mistake whenever the minimum is the middle value of the range, and the loop would no longer be guaranteed to find it.

Compare this with the search loop from earlier. The search can drop mid, because it has already checked mid against the target. The minimum finder cannot drop mid, because it has not yet proven that mid is not the answer. That one difference explains both loops, and it is a common interview question.

Common phrasings in interviews

The same idea is asked in several ways. You may be asked to find the rotation count, which is the index of the minimum. You may be asked for the largest value, which sits just before the minimum in a rotation. You may be asked for the target's index, or to say that it is missing. You may be asked to count how many values are below a target. Each version needs the rotation point first, so find the minimum before you do anything else, and then decide what you need from it.

A second method: find the minimum, then search in order

The rule you have learned is not the only way to solve the problem. A second method is more mechanical, and it reuses the minimum-finding loop. First find the rotation point p, which is the index of the minimum. Then pretend the array is not rotated at all. The logical position k in the sorted order lives at the real index (p + k) % n. An ordinary binary search can then run on the logical positions, and each probe maps back to a real index.

Take 4 5 6 7 0 1 2 and search for 6. The minimum is at index 4, so p = 4. The logical order is 0 1 2 4 5 6 7. The search on the logical order runs as usual, with lo = 0 and hi = 6. The middle is logical position 3, which is the value 4. Since 6 is bigger, the search moves right to logical position 5, which holds 6. The real index is (4 + 5) % 7 = 2, and a[2] is 6, which is correct.

The table shows the logical and real positions for the same probes.

This method makes two passes over the data: one to find the minimum and one to search. Both passes take O(log n), so the total is still logarithmic. Its advantage is that the search itself is a plain binary search, which you can check against the lesson on the basics. Its disadvantage is that it needs the minimum first, so it cannot be done in a single pass, and it does not help when the duplicates make the minimum search slow.

Comparing the two methods

The one-pass rule and the two-pass method both run in O(log n) on distinct values, and both use O(1) extra memory. The one-pass rule is shorter and handles the whole problem in one loop. The two-pass method is easier to explain step by step, and it lets you reuse two well-known pieces: the minimum finder and the plain search. In an interview, either is acceptable, as long as you explain what the loop decides at each step. Many candidates write the two-pass method first, then convert it to one pass when the interviewer asks for it.

Explaining the solution out loud

A good spoken answer has four short parts. First, say the key fact: at least one half of any range is sorted, because the array has one break. Second, say the decision: compare the middle with the left end to find the sorted half, then check whether the target falls inside it. Third, say the update: move the side that cannot hold the target, and keep the range inclusive. Fourth, say the edge cases you tested: one value, a rotation of zero, a target at either end, and a missing target. If the interviewer adds duplicates, say that the rule breaks, that you drop both ends in the ambiguous case, and that the worst case becomes O(n).

Practice

Work on paper first. Then check your code.

1. Trace the search for target 0 in 6 7 0 1 2 4 5. Write the table with lo, hi, mid, the value at mid, the sorted half and the decision.

2. Write a function that returns the number of rotations of a rotated sorted array with distinct values. For 3 4 5 1 2, the answer is 3.

int rotations(const vector<int>& a) {
    return findMinIndex(a);
}

3. Write a function that returns the index of the largest value in a rotated sorted array with distinct values. For 4 5 6 7 0 1 2, the answer is 3.

4. Find the minimum in a rotated sorted array that may contain duplicates. For 3 3 1 3, the answer is 1. Hint: when the middle equals the last value, you cannot decide which side holds the drop, so remove the last value.

int findMinDup(const vector<int>& a) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) lo = mid + 1;
        else if (a[mid] < a[hi]) hi = mid;
        else hi--;
    }
    return a[lo];
}

5. The code below is meant to search a rotated distinct array. It has one bug. Find it, and explain the input that breaks it.

bool search(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return true;
        if (a[lo] < a[mid]) {
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return false;
}

6. Prove, with a small example, that the search on duplicates can take about n steps. Use an array with n ones and one zero, placed so that the zero is in the middle of the rotation.

7. Count the values smaller than a target in a rotated sorted array with distinct values, in O(log n) time. For 4 5 6 7 0 1 2 and target 3, the answer is 3, because 0, 1 and 2 are smaller.

int countLess(const vector<int>& a, int target) {
    int n = (int)a.size();
    int p = findMinIndex(a);
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int v = a[(p + mid) % n];
        if (v < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

8. Using countLess from exercise 7, count the values v with L <= v <= R in a rotated sorted array with distinct values. For 4 5 6 7 0 1 2, L = 1 and R = 5, the answer is 4, because the values 1, 2, 4 and 5 qualify.

What you now know

• A rotated sorted array has one break, and at least one half of any range is always sorted.
• Decide which half is sorted by comparing a[lo] with a[mid], then test whether the target lies inside that sorted half.
• Use <= in the sorted-half test, so a one-value range is handled correctly.
• The minimum, which is the rotation point, is found by comparing a[mid] with a[hi] in a loop that uses hi = mid.
• Duplicates can hide which half holds the break. Dropping both ends in that case is safe, but the worst case becomes O(n).
• A brute-force check over all small cases catches most off-by-one errors quickly.