Sort then search in Python

Why this matters

Many questions about a list of numbers look at pairs, such as whether a value appears twice, whether two prices add up to a budget, or which reading is closest to a target. The simplest answer checks every pair. With 1,000 items, that is about half a million pairs, and with 100,000 items it is about five billion. Computer scientists write this cost as n squared, where n is the number of items. The word "squared" means the work grows with the square of the list size: double the list and the work becomes four times as large.

Sorting first changes the cost. A good sort takes about n log n steps, where log n is the number of times you can halve n before reaching 1. For 100,000 items, log n is about 17. After the list is sorted, many questions take one pass over the list, or about log n steps for each question. The total is much smaller than n squared.

This lesson shows the idea with four worked examples: finding a duplicate, finding two values with a target sum, finding the closest value, and counting values in a range. It also covers the bisect module, which searches a sorted list for you. The lesson before this one, on bad comparisons, explains how to make sure the sort itself is correct. Other lessons in this module cover sorting by two fields, and finding the top few items without sorting everything.

Why sorting helps

Think of a phone book. A name like "Patel" is easy to find, because the names are in alphabetical order. You open the book in the middle, see whether your name is before or after that page, and throw away half the book. You repeat this until you find the name or run out of pages. Now picture the same book with the pages shuffled. You would have to read every page.

Sorting gives a list the same kind of order. Two facts make it useful.

• Equal values end up next to each other. If a value appears twice, the two copies are side by side.
• Values that are close in size end up close in position. The value nearest a target sits right next to the spot where the target would go.

With those two facts, you can answer questions by looking only at neighbours, or by halving the range of positions you still need to check.

Example 1: finding a duplicate

Suppose you have the ages 42, 7, 19, 7, 3, 88 and want to know whether any age appears twice. The slow way compares each age with every other age. The sort-first way is shorter. Sort a copy of the list, then check each value against the one just before it. If two equal values exist, sorting has put them next to each other.

The output is:

ages: [42, 7, 19, 7, 3, 88]
has a duplicate: True
ages still in input order: [42, 7, 19, 7, 3, 88]
distinct: False

Three details matter here.

The function uses sorted(values), which makes a new list. Sorting the caller's list with values.sort() would change the order that the caller may depend on. The output shows the original ages list still in input order.

The loop starts at index 1 and compares copy[i] with copy[i - 1]. Index 0 has nothing before it, so the loop starts one step in.

The cost is the sort, about n log n, plus one pass of n comparisons. For 100,000 numbers, that is far less work than checking every pair, which would be about five billion comparisons.

Example 2: two values that add up to a target

Now a harder question. Given a sorted list of prices and a budget, find two prices that add up to exactly the budget. The brute-force method tries every pair. The sort-then-search method uses two pointers, which are just index numbers. One pointer starts at the smallest value, left, and the other starts at the largest value, right. Each step looks at the sum of the two values.

• If the sum equals the target, the pair is found.
• If the sum is too small, move left one step right. The value at left is the smallest one still in play, so any other pair that uses it would also be too small. Moving left is the only way to make the sum larger.
• If the sum is too big, move right one step left, for the same reason in reverse.

Each step throws away one value that cannot be part of an answer, so the walk finishes in at most n steps.

The output is:

sorted: [1, 3, 4, 7, 10, 15]
left=0 right=5 sum=16
left=0 right=4 sum=11
indexes for 11: (0, 4)
values: 1 and 10
indexes for 100: None

The first part of the program prints each step of the walk, so you can follow it. The sorted list is 1, 3, 4, 7, 10, 15. The first sum is 1 + 15 = 16, which is too big, so right moves from index 5 to index 4. The next sum is 1 + 10 = 11, which matches the target. The function pair_with_sum does the same walk and returns the indexes instead of printing.

Python integers have no size limit, so the sum total is always exact. In Java, the same sum with int values can wrap past the largest number and point the walk the wrong way. The Java version of this lesson casts one value to long to prevent that. The Python version needs no cast.

The function returns None when no pair exists, and the last line of output shows that.

Why the walk cannot miss a pair

Take the case where the sum is too big. The value at right is the largest one still in play. Every value from left onward is at least as big as the value at left. So if the value at right plus the value at left is already too big, the value at right plus any value from left onward is too big too. The value at right cannot be part of a pair, so it can be dropped. The same reasoning works for the case where the sum is too small. The walk drops values only when they cannot help, so it never misses the answer.

The next program traces the walk for a target of 17, which needs a pair that is not at the start of the list. Each line shows the two indexes and the sum.

The output is:

left=0 right=5 sum=16
left=1 right=5 sum=18
left=1 right=4 sum=13
left=2 right=4 sum=14
left=3 right=4 sum=17
found: 3 4

The walk moves left up when the sum is too small, and right down when it is too big. It finds the pair 7 and 10 after five steps, and it never looked at the pairs that could not work.

Example 3: the closest value and the smallest gap

Suppose a sorted list holds the readings from a sensor, and you want the reading closest to a target. Sorting puts the answer right beside the target's position. The bisect module has bisect_left, which finds the first position where the target would go, so that every value before that position is smaller than the target. The closest value is either the value at that position or the one just before it. The function compares the two.

The output is:

closest to 6: 7
closest to 9: 10
closest to 0: 1
closest to 99: 15
smallest gap in [90, 12, 47, 13, 200]: 1

bisect_left is a binary search. It keeps a range of positions, looks at the middle one, and throws away the half that cannot contain the answer. Each step halves the range, so the search takes about log n steps. You do not need to write the loop yourself, because the bisect module does it. The Java version of this lesson writes the loop by hand, and the idea is the same.

For the target 6, bisect_left returns position 3, which holds 7. The value before it is 4. The distance from 6 to 4 is 2, and the distance from 6 to 7 is 1, so the answer is 7. For the target 9, the neighbours are 7 and 10, and 10 is closer. Checking only these two neighbours is correct, because every other value is farther away than one of them on the same side.

smallest_gap shows the second use of sorting. The smallest difference between any two values in a list must be between two values that are next to each other in sorted order. If two values far apart had a smaller difference, a value between them would have to be even closer to one of them. So the function only compares neighbours.

Example 4: counting a range, and bisect on duplicates

Counting how many values fall between two limits is a common question. With a sorted list, the answer is the position just after the last value that is at most the upper limit, minus the position of the first value at or above the lower limit. The bisect module has two functions for this. bisect_left gives the position before the first equal value, and bisect_right gives the position after the last equal value.

The output is:

count from 20 to 50: 6
count from 36 to 49: 0
bisect_left for 2 in four 2s: 0
bisect_right for 2 in four 2s: 4

count_in_range(scores, 20, 50) counts the values 20, 20, 20, 35, 50 and 50, which is 6. The subtraction works because bisect_right for 50 is the position after the last 50, and bisect_left for 20 is the position of the first 20.

The two functions give different answers on duplicates, and both answers are fixed. For the four 2s, bisect_left returns 0, the first position of the value, and bisect_right returns 4, the position after the last one. Python's bisect promises which position you get, so you can rely on it.

Python's bisect module also has a rule to know. It assumes the list is already sorted. On an unsorted list it returns a position, and the position means nothing. The next program shows that case, together with a search that works on a sorted list of objects. The @dataclass line makes a class that only holds named fields, here id and total.

The output is:

bisect on unsorted [5, 1, 4, 9] for 5: 3
the value 5 is at index 0, and the `in` operator says: True
sorted: [('B2', 45), ('D4', 45), ('C3', 120), ('A1', 300)]
total 120 at index 2 C3
total 200 would be inserted at index 3

The first line is the silent error. The search returned 3 for a value that is at index 0. No error was raised, so the result looks like a position. The second line shows the right tool for a small unsorted list: the in operator checks every item, and it always gives the right answer.

The key argument to bisect_left tells the function which part of each object to compare. It was added in Python 3.10, and it works the same way as the key argument to sorted. The same key must be used for the sort and the search, so the two agree.

Common mistakes

Here are the errors this approach causes most often.

• Searching before sorting. A search on an unsorted list returns a position, and no error appears. In the example above, bisect_left returned 3 for a value that sits at index 0.
• Using the position from bisect as a found index without checking. bisect_left returns where the value would go, and the value may not be there. Check that pos < len(values) and that values[pos] == target before you trust the position.
• Assuming a search returns the last of several equal values. bisect_left returns the first position, and bisect_right returns the position after the last one. Pick the one that matches your question.
• Changing the order the caller depends on. Use sorted(values) to make a copy, as has_duplicate does, unless the caller expects the list to change.
• Off-by-one errors in the search range. bisect_right(values, hi) counts values up to and including hi. If you want values below hi, use bisect_left(values, hi) instead.
• Using a key for the sort and a different key for the search. The two must agree, or the search looks in the wrong place.

Practice

Exercise 1. Write a function that returns True when two values in a list are equal, and False otherwise. Do not use a nested loop. Say how many comparisons it makes for 1,000 values.

Show the answer

Sort a copy of the list, then compare each value with the one before it, as in has_duplicate. The sort makes about n log n comparisons, which is about 10,000 for 1,000 values, and the scan makes at most 999 more. A nested loop would make about 500,000 comparisons.

Exercise 2. The list [1, 3, 4, 7, 10, 15] is sorted. Trace pair_with_sum for the target 17. Write down each pair of indexes the walk visits and the sum at each step.

Show the answer

The walk starts at left=0 and right=5. The sum is 1 + 15 = 16, which is too small, so left moves to 1. Next, left=1 and right=5 gives 3 + 15 = 18, which is too big, so right moves to 4. Next, left=1 and right=4 gives 3 + 10 = 13, which is too small, so left moves to 2. Next, left=2 and right=4 gives 4 + 10 = 14, too small, so left moves to 3. Next, left=3 and right=4 gives 7 + 10 = 17, which matches. The function returns (3, 4). The trace program in this lesson prints the same five steps.

Exercise 3. Write closest_value for the list [2, 5, 9] and the target 6. Which value does it return, and why?

Show the answer

It returns 5. bisect_left for 6 returns position 2, which holds 9. The value before it is 5. The distance from 6 to 5 is 1, and the distance from 6 to 9 is 3, so 5 wins. The function only needs the two neighbours of the target's position, because every other value is farther away.

Exercise 4. A list of readings is sorted. Write an expression that counts the readings that are greater than 100 and at most 200. Use the bisect module.

Show the answer

The values greater than 100 start after the last 100, which is bisect_right(readings, 100). The values at most 200 end at the last 200, which is bisect_right(readings, 200). So the count is bisect.bisect_right(readings, 200) - bisect.bisect_right(readings, 100).

Exercise 5. Sort a list of students by name, then check whether two students share the same name. Explain why the adjacent check is enough, without looking at every pair.

Show the answer

After sorting by name, all students with the same name are next to each other, because the sort puts equal names side by side. A duplicate name therefore always shows up as two neighbours with equal names. If a name appeared twice but was not next to its copy, the sort would have placed another name between them, which would mean the sort is wrong.

Summary

• Sorting a list once costs about n log n steps, and then many pair and range questions take one pass or about log n steps each.
• Equal values end up next to each other after a sort, so a duplicate check compares only neighbours.
• Two pointers walk inward from both ends. Each step drops one value that cannot be part of an answer.
• The bisect module does a binary search. bisect_left gives the first position of a value and bisect_right gives the position after the last one.
• bisect returns a position on an unsorted list without any error, so sort before you search.
• Use sorted(values) to make a copy when the caller depends on the original order.