Rotated array search and counting inversions in Python

Why it matters

Interviewers like these two problems because each one is a well-known algorithm with a single twist. If you understand the base algorithm, the twist is a small change. If you do not, the twist looks like a new problem, and you may freeze. This lesson teaches you to spot the twist, reason about it step by step, and write the code with confidence.

The first problem is searching a rotated sorted list. It is a binary search where the usual rule that the whole list is sorted no longer holds, but a weaker rule still does. The second problem is counting inversions, which measure how far a list is from sorted order. You solve it by reusing the merge step of merge sort, so the work you did in the previous lesson pays off here.

You need binary search from the first lesson of this module, merge sort from the second, and the habit of tracing code by hand. You do not need quick sort for this lesson.

Part one: the rotated list

A sorted list is rotated when some of its tail moves to the front. Start with the sorted list [0, 1, 2, 4, 5, 6, 7]. Move the last four values, 4 5 6 7, to the front. The result is [4, 5, 6, 7, 0, 1, 2]. The rotation point, where the sorted order breaks, sits between 7 and 0.

Think of a clock face on a wall. The numbers go around in order from 12 back to 12. If you spin the clock, the numbers still go around in order, but the starting point has moved. A rotated list is the same idea: the values still go up in a cycle, and the break sits somewhere you do not know yet.

Assume for now that every value is different. The problem is to find a target in the rotated list in O(log n) time. A plain search from the front would take O(n), so the goal is a binary search. The difficulty is that the whole list is no longer sorted, so the rule that let you throw away half of it no longer applies directly.

Look at the two halves of any range and see which one is still in order. Here is the key fact that makes a search possible.

The key fact that makes it work

Pick the middle index mid. Even though the whole list is not sorted, at least one of the two halves, left from lo to mid or right from mid to hi, is sorted. The break can be in only one of them, because a rotation has only one break point. The other half is an unbroken run of increasing values.

Once you know which half is sorted, you can test whether the target lies inside that sorted half. If it does, search there. If it does not, the target must be in the other half, and that half may still hold the break, so search there. In both cases you throw away one half, which is the halving step you know.

Here is the exact test. If a[lo] is less than or equal to a[mid], the left half is sorted, because its first value is not bigger than its middle value and the values in between cannot break the order. Otherwise the right half must be sorted. The method checks whether the target falls in the sorted half using the endpoints of that half. For the left half, the target is in range when it is at least a[lo] and less than a[mid]. For the right half, it is in range when it is bigger than a[mid] and at most a[hi].

Python lets you write that range test as one line, a[lo] <= target < a[mid]. This is called a chained comparison. It means the same as a[lo] <= target and target < a[mid].

The precise version

Read the function below. It is a binary search with one extra decision at each step.

The output is:

target 0 index 4
target 3 index -1
target 4 index 0
target 2 index 6
target 7 index 3

The first check is the same as in plain binary search: if a[mid] is the target, return it. The second check, a[lo] <= a[mid], decides which half is sorted. The third check tests whether the target lies in the sorted half. If it does, the search keeps that half. If not, it keeps the other half. The <= in the first decision matters. When lo equals mid, the left half is a single value, which counts as sorted, and the <= makes that case take the left branch correctly.

The middle index is written (lo + hi) // 2. The // symbol divides and drops the remainder. Python integers do not overflow, so you do not need the lo + (hi - lo) // 2 form that some other languages use to avoid overflow.

Trace the search for 0. The range is 0 to 6, and mid is 3, which holds 7. The left half, 4 5 6 7, is sorted, since a[0] is 4 and that is not bigger than 7. Is 0 in the range from 4 up to but not including 7? No. So the target must be in the right half, and the function sets lo to 4. Now the range is 4 to 6, and mid is 5, which holds 1. Here a[4] is 0, which is not bigger than 1, so the left part 0 1 is sorted. Is 0 in the range from 0 up to but not including 1? Yes. So the function sets hi to 4. The range is now 4 to 4, mid is 4, and a[4] is 0. Found.

Now watch the same kind of search with the visualizer. It runs binary search on a sorted list, and the same halving steps apply here after you know which half to keep.

After the animation, think about the rotated version. The steps are the same, but each one has an extra check to see which half is in order.

Working a search on paper

You can check the rotated search by hand with a table, the same way you checked the merge. Use the list [4, 5, 6, 7, 0, 1, 2] and the target 5. Each row is one pass of the loop.

Now search for 1. This time the table has two passes.

The rule for each row is the same. If the sorted half's range contains the target, keep that half. Otherwise keep the other half. When a row goes wrong in your own table, you can see exactly which check failed.

Tracing a target that is missing

The rotated search gives -1 for a missing target, and the reason is worth tracing, because it is the same reason the plain binary search gives -1. Search for 3 in [4, 5, 6, 7, 0, 1, 2].

• Step 1: lo 0, hi 6, mid 3, value 7. Is the left half sorted? a[0] is 4, which is not bigger than 7, so yes. Does its range cover 3? The range runs from 4 up to but not including 7, so no. So lo becomes 4.
• Step 2: lo 4, hi 6, mid 5, value 1. Is the left half sorted? a[4] is 0, which is not bigger than 1, so yes. Does its range cover 3? It runs from 0 up to but not including 1, so no. So lo becomes 6.
• Step 3: lo 6, hi 6, mid 6, value 2. The left half is a single item, so it counts as sorted. Does its range cover 3? It runs from 2 up to but not including 2, which is empty, so no. So lo becomes 7.
• Now lo is past hi, so the loop stops and the function returns -1.

In each step, the sorted half's range did not cover 3, so 3 could not be in that half, and the function moved to the other half. That is the rule that makes the search correct. Three checks were enough to prove that 3 is missing. The same kind of proof works for the plain binary search, and it is why both methods can answer "not found" in O(log n) time.

Worked example: finding the smallest value

A useful companion problem is finding the smallest value in a rotated list. The smallest value is the rotation point, the place where the order breaks. If the list was not rotated, the smallest value is the first one. The function below compares a[mid] with a[hi] instead of with a target.

Here is the reasoning. If a[mid] is bigger than a[hi], the break must lie to the right of mid, because the values from mid to hi cannot be in order. So the smallest value is in the right part, and you can throw away the left part, including mid. Otherwise a[mid] is not bigger than a[hi], so the values from mid to hi are in order, and the smallest value may be at mid itself or to its left. You keep mid in the range.

The output is:

minimum 0
minimum 1
minimum 1
minimum 1
minimum 7

Look at the loop condition. This function uses lo < hi, not lo <= hi, because the answer is a position that the range has to narrow down to one index. When lo and hi meet, that index holds the smallest value. The case [1, 2, 3, 4, 5] is worth tracing: the list is not rotated, so a[mid] is never bigger than a[hi], and hi keeps moving left until it reaches index 0.

Trace [3, 4, 5, 1, 2]. The range is 0 to 4, and mid is 2, holding 5. Is 5 bigger than the last value 2? Yes, so the answer is to the right, and lo becomes 3. The range is 3 to 4, and mid is 3, holding 1. Is 1 bigger than 2? No, so hi becomes 3. The range is now a single index, 3, which holds 1. Return 1.

Part two: counting inversions

Now the second problem. An inversion is a pair of positions i and j where i is less than j, but the value at i is bigger than the value at j. In plain words, a bigger number sits before a smaller one. In the list [2, 4, 1, 3, 5], the inversions are the pairs (2, 1), (4, 1) and (4, 3). The count is 3.

Inversions measure how far a list is from being sorted. A sorted list has zero inversions. The reversed list of n items has the most: every pair is out of order, which is n times n minus 1 divided by 2. Ranking systems use this measure. If two rankings of the same players have n players, the number of inversions between them is a standard distance between the two rankings, and a small number means the rankings agree.

The direct method checks every pair, which takes O(n squared) time. You can do better by using the merge step of merge sort. The key observation is this. While merging two sorted halves, suppose the next item to take comes from the right half. It is smaller than every item still waiting in the left half, because the left half is sorted. Each waiting left item therefore forms an inversion with the right item. The merge can count them in one step: add the number of waiting left items.

The precise version

Here is merge sort with the counting added. It returns the number of inversions and a sorted list, so it does two jobs at once. Each call slices the list into two new lists, so this version does not change the list you pass in.

The output is:

(3, [1, 2, 3, 4, 5])
(10, [1, 2, 3, 4, 5])

The first answer is 3, as counted by hand. The second answer is 10, which is 5 times 4 divided by 2, the largest possible count for five items. Both calls return the list in sorted order, because the function is merge sort underneath.

Look at the line count += len(left) - i. It runs only in the else branch, when the item taken comes from the right half. At that moment, i points to the next unused item of the left half, and every item from i to the end of left is still waiting. There are len(left) - i of them, and each one is bigger than the right item, so each forms an inversion with it.

Only the else branch counts, and the <= decides which branch runs for equal values. When the left and right items are equal, the left one goes first and nothing is counted. That is correct, because equal values are not out of order. Strictly bigger values before smaller ones are the only inversions.

The slices a[:mid] and a[mid:] make copies. Copying takes extra memory and time, but the total work is still O(n log n), because each level of the recursion copies about n items. Python integers grow as large as needed, so the count never overflows. In a language with fixed-size integers, the count for a large list would need a bigger type.

Tracing the count by hand

Walk through one merge by hand. Merge the sorted left half [2, 4] with the sorted right half [1, 3, 5], which is the kind of merge that happens inside the recursion.

Compare the fronts, 2 and 1. The smaller is 1, from the right. The left items still waiting are 2 and 4, so two inversions are added: the pairs (2, 1) and (4, 1). Compare 2 and 3. The smaller is 2, from the left, so no count. Compare 4 and 3. The smaller is 3, from the right, and only 4 is still waiting, so one inversion is added: the pair (4, 3). Compare 4 and 5. The smaller is 4, from the left, and then the left half is empty, so 5 is copied. The total from this merge is 3.

The recursion on the full list gives the same total. The top call splits the list into [2, 4] and [1, 3, 5], and its merge is the one traced above. The merges below it add nothing, because in each of them every left item is smaller than the right item. Everything agrees.

Now watch the merge steps run in the visualizer. It shows the merged runs growing, the same process you saw in merge sort.

Counting with a number you type

The next program reads a list of numbers from the keyboard and prints the count. It uses the same counting function as above, with input added. This program reads input, so it is not a run-in-place example. Save it as inversions.py and run it with python3 inversions.py, then type the lines when the program asks.

def count_inversions(a):
    if len(a) <= 1:
        return 0, list(a)
    mid = len(a) // 2
    left_count, left = count_inversions(a[:mid])
    right_count, right = count_inversions(a[mid:])
    count = left_count + right_count
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            count += len(left) - i
    merged.extend(left[i:])
    merged.extend(right[j:])
    return count, merged
 
 
n = int(input())
values = [int(x) for x in input().split()]
count, _ = count_inversions(values)
print("inversions:", count)

Type these lines when the program asks, one line at a time:

5
2 4 1 3 5

The output is:

inversions: 3

Try a second run with 5 and then 5 4 3 2 1. The output is inversions: 10. The underscore in count, _ = ... is a name for a value you do not need. The function also returns the sorted list, and this program throws it away.

Why the fast count matters

Compare the two methods on bigger inputs. The brute force method checks n times n minus 1 divided by 2 pairs. The merge method takes about n times log base 2 of n steps. The gap grows quickly.

For 100,000 items, the brute force method makes about five billion pair checks. Python runs about tens of millions of simple steps per second, so that takes minutes. The merge method makes about 1.7 million steps, which takes a fraction of a second. The difference grows with every doubling of the input, which is why the merge step is worth the extra code.

Inversions in reversed lists

The reversed list is the extreme case, because every pair is out of order and the count is at its largest. The next program counts the inversions of the reversed lists of length 1 to 6. It builds each list as n down to 1 and runs the same counting function.

The output is:

reversed, n = 1: 0 inversions
reversed, n = 2: 1 inversions
reversed, n = 3: 3 inversions
reversed, n = 4: 6 inversions
reversed, n = 5: 10 inversions
reversed, n = 6: 15 inversions

Look at the pattern: 0, 1, 3, 6, 10, 15. Going from a reversed list of n minus 1 items to one of n items adds a new largest value at the front. That front value is bigger than every item after it, so it adds n minus 1 inversions. The total is therefore the sum 0 + 1 + ... + (n minus 1), which equals n times n minus 1 divided by 2. The program prints the word "inversions" even when the count is 1. That is fine for a lesson, but a polished program would choose the singular form.

Testing the fast method against the slow one

A fast method is only useful if it is right. The safest test compares it with a simple, slow method that you trust. The slow method checks every pair, which is easy to get right. The next program generates 500 random lists, with values from -20 to 20, and checks that the two methods agree on every one. The random generator has a fixed seed, so the test is the same on every run.

The output is:

agreed on 500 of 500 random lists

The brute function uses a generator expression inside sum(). It adds 1 for each pair that is out of order, without building a list. The values are between -20 and 20, so there are only 41 possible values in up to 40 slots. Duplicates are common, and they are the case most likely to break a counting method. The fast method treats equal values as in order, the same way the brute force method does, so the two agree. If you changed the merge's <= to <, the test would catch it, because equal values would then be counted as inversions and the totals would differ. Writing such a test is good practice for any algorithm with a subtle comparison.

Rotated search with input

The rotated search also reads its input from the keyboard. The first number is the length of the list, then come the values in rotated order, and then the target. This program prints the index or -1. Like the counting program above, it is not a run-in-place example. Save it as rotated_search.py.

def search_rotated(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1
 
 
n = int(input())
values = [int(x) for x in input().split()]
target = int(input())
print("index", search_rotated(values, target))

Type these lines when the program asks, one line at a time:

7
4 5 6 7 0 1 2
0

The output is:

index 4

Change the last line to 3, and the output is index -1, because 3 is not in the list. Try a few more targets on your own, and check each answer against the list by eye. This is the fastest way to build trust in a search method.

Duplicates break the plain search

Everything so far assumed that the values are all different. Real data often has repeats, and repeats break the plain rotated search. The reason is that a[lo], a[mid] and a[hi] can be equal, so the <= test cannot tell which half is sorted.

Here is a run of the plain method on [1, 0, 1, 1, 1], looking for 0, which sits at index 1. The fixed version adds one step: when a[lo], a[mid] and a[hi] are all equal, the function checks the two ends, then moves both ends in by one and tries again.

The output is:

plain for 0: -1
fixed for 0: 1

The plain method says 0 is missing. At the start a[0], a[2] and a[4] are all 1, so the left half looks sorted, and the target 0 is then thrown away. The fixed version is safe because neither end holds the target, and the middle was already checked. Dropping both ends removes only values that are not the target. In the worst case, almost every step takes the extra branch, so the time becomes O(n).

Mistakes and what they produce

Each of these two problems has traps. Learn to recognize them.

Mistake 1: using < where the code needs <= in the sorted-half check. When lo and mid are the same index, the left half is one item. That half is sorted, but a[lo] < a[mid] is false, so the code would treat the right half as the sorted one and could skip the target. Here is the strict version run on the list [2, 1], looking for 1, which sits at index 1:

The output is -1, which is wrong. Use <= in that check.

Mistake 2: expecting the input list to change. The counting function from this lesson returns a new sorted list and leaves the input as it was. A common mistake is to call the function and then print the original list, expecting it to be sorted. In the version that uses slices, the input is not changed:

a = [2, 4, 1, 3, 5]
count, result = count_inversions(a)
print("input unchanged:", a, "result:", result, "count:", count)

The output is:

input unchanged: [2, 4, 1, 3, 5] result: [1, 2, 3, 4, 5] count: 3

Use the second value that the function returns. Also note that the function needs the count_inversions definition from above in the same file.

Mistake 3: counting on the wrong branch. The count must add in the right-half branch only. If you add in the left-half branch, you count pairs in the wrong direction, and the answer is wrong in a silent way. Check your counting code with the five-item example, which has a known answer of 3.

Mistake 4: a wrong index in the counting formula. The formula len(left) - i counts the waiting left items. A common error is writing len(left) - 1 - i, which misses the item at i itself and gives a count that is one too small. The debugging walkthrough below shows the effect.

Mistake 5: a big count stored in the wrong type. Python integers grow as needed, so the count never overflows. Other languages use fixed-size integers, and a count of n times n minus 1 divided by 2 can overflow them for large n. If you read a count from a file or a database, check that the stored type can hold the number.

Debugging walkthrough: a count that is one too small

Suppose a teammate's version prints 0 for the list [3, 1], but the answer is 1. A pair of two items is the simplest case, so start there.

Trace the code by hand on [3, 1]. The range is 0 to 1, and mid is 0. The left half is [3] and the right half is [1]. The merge compares 3 with 1. The condition left[i] <= right[j] is false, so the else branch runs and takes 1. The 3 is still waiting in the left half, so the count should go up by one. Here is the else branch the teammate wrote, with the same function as before:

The output is:

wrong formula on [3, 1]: 0
wrong formula on [2, 3, 1]: 0

With i at 0 and left holding one item, the formula len(left) - 1 - i gives 0, so the count stays at 0. The correct formula is len(left) - i, because the item at i is also waiting and also bigger than the right item. With that change, [3, 1] gives 1 and [2, 3, 1] gives 2, which matches the count by hand.

The lesson for debugging is this. When a count is off by a small amount, write the smallest input that shows the problem, trace it on paper, and compare each variable with what you expected. A two-item example is often enough, and it takes less time than changing code at random.

Real-world uses and interview questions

Counting inversions has practical uses. When two rankings of the same items are compared, the number of inversions between them is a standard measure of how much the rankings disagree. A count of zero means the rankings agree exactly.

Interviewers ask about these problems in several forms.

• "Find the minimum in a rotated sorted list." Explain the comparison with a[hi], and why lo < hi ends with the answer.
• "Search in a rotated list with duplicates." Explain why the plain method can return a wrong answer, and describe the extra step that shrinks both ends when the endpoints and middle are equal. Say that this makes the worst case O(n).
• "Count inversions." Explain the merge trick, why each waiting left item forms one inversion, and why the time is O(n log n).
• "How would you test it?" Describe the brute-force comparison with random inputs and duplicates, as in this lesson.

Practice

Try each exercise on your own before you open the solution.

1. Find the index of the smallest value in [4, 5, 6, 7, 0, 1, 2]. Hint: the answer is the index of 0.

2. Count the inversions of [3, 1, 2] by listing the pairs. Then check your answer with the merge method. Hint: the pairs are (3, 1) and (3, 2).

3. How many inversions does [5, 4, 3, 2, 1] have? Hint: the formula is n times n minus 1 divided by 2.

4. Explain why count += len(left) - i counts the waiting left items, using the words "sorted" and "waiting" in your answer. Hint: the left half is already in order when the merge starts.

5. Write a function that returns True if a rotated list contains the target, without returning the index. Hint: call search_rotated and check whether the result is not -1.

6. Count the inversions in a list that is already sorted. What does the merge do, and what is the total? Hint: the else branch never runs.

7. Write a function that counts the pairs where the first item is bigger than the second, but only for adjacent positions. Explain why this is much smaller than the inversion count. Hint: each pair is only two positions apart.

8. Find the rotation amount, meaning how many steps the list was rotated from sorted order, using the minimum search. Hint: the answer is the index of the minimum.

9. Modify count_inversions so it prints each pair it counts, in the form (left value, right value). Run it on [2, 4, 1, 3, 5]. Hint: when the right item is taken, print one pair for every item from left[i:], each paired with right[j], before j moves.

10. Run the plain rotated search on [1, 0, 1, 1, 1] with target 0, and explain why it returns -1. Then explain why the extra step that moves both ends in by one fixes this. Hint: look at a[lo], a[mid] and a[hi] on the first pass.

Show the answer

1. The smallest value is 0, at index 4. The answer is 4.

Show the answer

2. The pairs with the bigger number first are (3, 1) and (3, 2). The pair (1, 2) is in order. So there are 2 inversions. The merge method gives the same answer: the 1 is taken from the right half while the 3 is waiting, adding 1, and then the 2 is taken from the right half while the 3 is waiting, adding 1.

Show the answer

3. The count is 5 times 4 divided by 2, which is 10. Every pair is out of order, because the list is in reverse order.

Show the answer

4. In the merge, both halves are sorted before the merge starts. When the right item is smaller than the left item at i, it is also smaller than every item after i in the left half, because the left half is sorted. Those items from i to the end of left are waiting. There are len(left) - i of them, and each one forms an inversion with the right item.

Show the answer

5. Return search_rotated(a, target) != -1. The function already handles every case, so the wrapper is one line. This is a good example of reusing a function rather than rewriting it.

Show the answer

6. The list is already in order, so every right item is bigger than or equal to every left item. The else branch never runs, so the count adds nothing. The total is 0.

Show the answer

7. Loop from index 0 to len(a) - 2. Count when a[i] is bigger than a[i + 1]. This only counts adjacent pairs, so it is at most n minus 1, while the inversion count can reach n times n minus 1 divided by 2. Adjacent pairs are a smaller and simpler measure.

Show the answer

8. Find the index of the minimum with find_min. For [4, 5, 6, 7, 0, 1, 2] the minimum 0 is at index 4, so the list was rotated by 4 steps from the sorted order. The answer is 0 when the list is not rotated at all.

Show the answer

9. Inside the else branch, before j += 1, loop over the values in left[i:] and print each one with right[j]. For [2, 4, 1, 3, 5] the lines are the pairs (2, 1), (4, 1) and (4, 3). The left values must come from left[i:], because those are the items still waiting.

Show the answer

10. The first pass checks lo 0, hi 4, mid 2. The values at 0, 2 and 4 are all 1, and the middle is not 0. Since a[lo] is not greater than a[mid], the code assumes the left half is sorted. The target 0 is not inside the range from 1 up to but not including 1, so the code sets lo to 3 and never looks at index 1 again, which holds the 0. The function returns -1. The fix checks the three values first. When all three are equal, none of the ends can be the target, because the middle was already compared with the target. Moving both ends in by one is therefore safe, and on this list the fixed version finds 0 at index 1.

What you now know

• A rotated sorted list still has one sorted half at each step, and you can use that half to decide which side to keep.
• Use a[lo] <= a[mid] to find the sorted half, then test whether the target is inside its range.
• With duplicates, the plain rotated search can give a wrong answer. Shrinking both ends when the endpoints and middle are equal fixes it, at O(n) worst-case time.
• To find the minimum of a rotated list, compare a[mid] with a[hi] and keep the side that holds the break.
• An inversion is a pair where a bigger value comes before a smaller one. A sorted list has zero.
• The merge step of merge sort counts inversions. When a right item is taken, add the number of left items still waiting, which is len(left) - i.
• The function takes O(n log n) time and O(n) extra memory for its copies. Python integers do not overflow, so the count can grow as large as it needs.