Ordered lookups with bisect

Why this matters

A dict answers one kind of question very fast: "is this key here, and what is its value?" It does not answer questions about position. Suppose a bus timetable has departures at 09:00, 12:30, 15:00 and 18:00. A passenger arrives at 14:00 and asks, "what is the last bus before now?" A dict can only find buses by their exact time. It cannot find the nearest one without checking every entry.

A sorted structure answers that question directly. The keys stay in order, so the program can jump to the right place and read the answer. Python's standard library has no sorted map and no balanced tree. It does have the bisect module, which searches a sorted list in O(log n) steps. O(log n) means the number of steps grows by one each time the list doubles in size. This lesson uses a sorted list and bisect to build the same answers.

The hash-based lessons before this one explain how a dict finds a key. This lesson is about the opposite trade-off: order is slower to maintain, but it gives answers a dict cannot give.

Words you need first

An ordered collection keeps its items sorted by key, from the smallest to the largest. Keeping a list sorted costs extra work on every insert, so it is slower than a dict for plain lookups.

A range lookup asks about keys between two values, such as "how many events happened between 09:00 and 12:00?"

The floor of a value x is the largest key that is less than or equal to x. The ceiling of x is the smallest key that is greater than or equal to x. If x is itself a key, both the floor and the ceiling are x.

The position of a value in a sorted list is its index. The bisect functions return positions, and you read the key at that position.

The idea first: a sorted list and a halving search

Take a sorted list of four departure times in minutes after midnight: [540, 750, 900, 1080]. That is 09:00, 12:30, 15:00 and 18:00. The question is: what is the last departure at or before 14:00, which is minute 840?

You can answer by looking at the middle. The middle of four items is between the second and third. The third item, 900, is later than 840, so the answer must be on the left. The left half is [540, 750]. Its last item, 750, is earlier than 840, so 750 is the answer.

Each check throws away half of the remaining items. This is called a binary search. With four items you need at most two checks. With a million items you need at most about 20. The sorted order is what makes this work: because everything to the right of the middle is larger, you never need to look there.

The bisect module does this search for you. There are two functions. bisect.bisect_left(keys, x) returns the position where x would go, before any equal values. bisect.bisect_right(keys, x) returns the position where x would go, after any equal values. Every neighbour question in this lesson comes down to one of these two positions and a check on the key next to it.

Four neighbours with bisect

The four neighbours of a value are the floor, the ceiling, the strictly lower key and the strictly higher key. Each one is a position, a step left or right, and a check that the position is inside the list. The times in the code below are written as HHMM numbers, so 1230 means 12:30.

The output is:

floor_key(1400) = 1230
ceiling_key(1400) = 1500
floor_key(1500) = 1500
ceiling_key(1500) = 1500
floor_key(800) = None
ceiling_key(2000) = None
event at floor: lunch
lower_key(1500) = 1230
higher_key(1500) = 1800

Read the lines one at a time. At 14:00 the current event is lunch, because 1230 is the largest key at or before 1400. The next event is the review at 1500. When the time is exactly a key, floor_key and ceiling_key both return that key. The strict versions, lower_key and higher_key, skip it. Use the strict versions when the key itself must not count, for example "the previous event, not this one".

The function floor_key(800) returns None because nothing starts at or before 08:00. The function ceiling_key(2000) returns None because nothing starts at or after 20:00. The check if i >= 0 and if i < len(keys) is what produces these answers. Without the checks, the program would read a position that does not exist.

The events dict is still the place where the values live. The sorted list keys only holds the order. Keep the two in step: when you add a new key, insert it into the sorted list with bisect.insort and store the value in the dict.

A price in effect, and counting a range

A price history is a map from the minute a price starts to the price. The price in effect at any minute is the one with the largest start time at or before that minute. That is floor_key.

The second function counts how many keys fall in a range [lo, hi], both ends included. In a sorted list this does not need a loop. The number of keys that are at most hi is the position just after hi. The number of keys that are less than lo is the position of lo. The difference is the count.

The output is:

minute 3: 10.00
minute 5: 12.50
minute 20: 11.25
minute -1: no price yet
keys in [4, 15]: 4
keys in [10, 14]: 0
keys in [30, 40]: 0

Check the range count by hand. The keys are 2, 4, 7, 9, 15 and 21. Between 4 and 15 inclusive are 4, 7, 9 and 15, which is four keys. Between 10 and 14 there are none. Between 30 and 40 there are none.

The count takes two binary searches, so it costs O(log n) no matter how many keys are in the range. A version that walks the keys one at a time would cost one step for each key in the range. The max(0, ...) guard handles a range where lo is larger than hi, which would otherwise give a negative count.

The closest value

A set of stored values is a sorted list with no values attached. Here is a harder case. Given the stored values, find the one closest to a target. The answer could be the floor or the ceiling, so the function checks both and compares the distances. It must also handle a missing side, where the floor or the ceiling is None.

The output is:

closest to 5 : 10
closest to 30 : 25
closest to 32 : 25
closest to 33 : 40
closest to 55 : 70
closest to 100 : 70
empty list: None

Check 55 by hand. The floor is 40, which is 15 below 55. The ceiling is 70, which is 15 above 55. The distances are equal. The code uses below if target - below < above - target else above, which picks the ceiling on a tie, so it returns 70. This is the larger value. A different tie rule would also be valid, but it would return 40.

Common mistakes

Reading keys[i - 1] when i is 0. In Python, a negative index counts from the end of the list. So keys[-1] is the last key, and it is returned without any error. The program then gives a wrong answer that looks right. This is the most dangerous mistake in this lesson. Always check i >= 0 before you read keys[i]. The next example shows the wrong answer:

The output is:

keys[i - 1] with i = 0 gives 1230

The answer 1230 is the last key, not a key before 900. Python returns it because -1 is a valid index. The fix is the check if i >= 0 else None, used in the functions above.

Calling a floor method on a dict. A dict has no floor, ceiling, lower or higher method. Calling one gives this error:

AttributeError: 'dict' object has no attribute 'floor'

Read the message from the right. The object is a dict, and a dict has no such method. The fix is to keep a sorted list of the keys and use bisect on that list, as the functions above do.

Putting None in a sorted list. A sorted list must compare each new item with the items already there. It cannot compare None with a string or a number. Inserting None into a list of numbers gives this error:

TypeError: '<' not supported between instances of 'NoneType' and 'int'

A dict accepts None as a key, but the sorted list does not. Use real keys only, and check for None before you insert.

Using bisect on a list that is not sorted. bisect assumes the list is in order. On an unsorted list it returns a position without any error, and the position is wrong. In the next example, the list [5, 1, 3] is not sorted, and bisect_left returns 2, which is not where 3 belongs in that list:

The output is:

unsorted bisect_left(3): 2

Sort first, with sorted(...) or by inserting with bisect.insort, so the list stays in order.

Forgetting to update both parts. When the sorted list and the dict hold different things, adding a key to one and not the other breaks the lookups. Add new keys with bisect.insort(keys, key) and with dict[key] = value in the same place.

Changing a key after it is stored. The sorted list places each key by its value at insert time. If you change that value later, the list no longer has the key in the right place. Use keys that never change, such as numbers, strings or tuples of them.

Mixing up the strict and non-strict versions. floor_key(1500) returns 1500, because the key is equal and counts. lower_key(1500) returns 1230, because it must be strictly less. Pick the version that matches the question. "The event that is current at 15:00" uses floor_key. "The event before the review" uses lower_key.

bisect and the C++ names

The same two functions exist in C++ as std::lower_bound and std::upper_bound, which work on sorted ranges. The Python names are bisect_left and bisect_right. The meaning is the same:

• bisect_left(keys, x) is the position of the first key that is at least x. That is the position for the ceiling.
• bisect_right(keys, x) is the position just after the last key that is at most x. The key before that position is the floor.

When the position is at the end of the list, there is no answer. Check the length before you read the key, as the functions above do.

Practice

1. A sorted list of keys holds 10, 20 and 30. What does floor_key(5) return? Write the line of code that prints "none" when the answer is None.

   Show the answer: floor_key(5) returns None, because no key is at or below 5. The code is:

   Copy

   k = floor_key(5)
   print("none" if k is None else k)

   The check uses is None, which is the right test for None. Reading keys[-1] here would return 30, which is the wrong answer.

2. The sorted list [1, 3, 3, 3, 5] holds three copies of 3, at indexes 1, 2 and 3. Which index does bisect_left(keys, 3) return, and which index does bisect_right(keys, 3) return? Use the two indexes to count the 3s.

   Show the answer: bisect_left returns index 1, the first 3. bisect_right returns index 4, the position of the 5. The number of 3s is the difference, 4 minus 1, which is 3.

3. A sorted list holds exam scores. Write a function lowest_pass that returns the lowest score that is at least 60, or -1 if no score qualifies.

   Show the answer:

   Copy

   def lowest_pass(scores):
       i = bisect.bisect_left(scores, 60)
       return scores[i] if i < len(scores) else -1

   The function checks the length before it reads the score, so an empty list or a list with only low scores returns -1 and does not raise an error.

4. Write a function largest_at_most that takes a sorted list and a value x, and returns the largest item that is at most x, or -1 if there is none.

   Show the answer:

   Copy

   def largest_at_most(items, x):
       i = bisect.bisect_right(items, x)
       return items[i - 1] if i > 0 else -1

   For the list [2, 4, 7] and x = 5, bisect_right returns 2, the position of 7. The item before it is 4, and the function returns 4.

5. A room booking system stores each booking as a start time mapped to an end time, in a dict. Write a function is_busy that returns True when some booking covers time t, meaning its start is at or before t and its end is after t. Use one search.

   Show the answer:

   Copy

   def is_busy(starts, bookings, t):
       i = bisect.bisect_right(starts, t) - 1
       if i < 0:
           return False
       return bookings[starts[i]] > t

   Here starts is the sorted list of start times. The booking that could cover t is the one with the largest start at or before t. That is the floor. The function assumes the bookings do not overlap, which the question's wording implies.

Summary

• A sorted structure answers position questions that a dict cannot: the nearest key below or above a value, and the keys in a range.
• Python has no sorted map in its standard library. Use a sorted list of keys with bisect, and keep a dict for the values.
• bisect_right minus one gives the floor. bisect_left gives the ceiling. The strict versions shift the position by one.
• A position of -1 or the length of the list means no answer. Check it before you read the key, because keys[-1] returns a real key without any error.
• Counting keys in a range is two binary searches and a subtraction.
• bisect needs a sorted list. On an unsorted list it returns a wrong position without warning.