Working with Sorted Lists in Python: Magic of the `bisect` Module

Working with sorted lists can sometimes be a bit tricky. You need to maintain the order of the list after each insertion and efficiently search for elements within it. Binary search is a powerful algorithm for searching in a sorted list. While implementing it from scratch isn’t too difficult, it can be time-consuming. Fortunately, Python offers the bisect module, which makes handling sorted lists much easier.

What Is Binary Search?

Binary search is an algorithm that finds the position of a target value within a sorted array. Imagine you are searching for a name in a phone book. Instead of starting from the first page, you likely begin in the middle of the book and decide whether to continue searching in the first or second half, based on whether the name is alphabetically greater or less than the one in the middle. Binary search operates in a similar manner: it starts with two pointers, one at the beginning and the other at the end of the list. The middle element is then calculated and compared to the target.

The bisect Module: Simplifying Sorted List Operations

While binary search is effective, writing out the implementation every time can be tedious. But what if you could perform the same operations with just one line of code? That’s where Python's bisect module comes in. Part of Python's standard library, bisect helps you maintain a sorted list without needing to sort it after each insertion. It does so using a simple bisection algorithm.

The bisect module provides two key functions: bisect and insort. The bisect function finds the index where an element should be inserted to keep the list sorted, while insort inserts the element into the list while maintaining its sorted order.

Using the bisect Module: A Practical Example

Let's start by importing the module:

import bisect

Example 1: Inserting a Number into a Sorted List

Suppose we have a sorted list of numbers:

data = [1, 3, 5, 6, 8]

To insert a new number while keeping the list sorted, simply use:

bisect.insort(data, 7)

after running this code, data will look like this:

[1, 3, 5, 6, 7, 8]

Example 2: Finding the Insertion Point

What if you just want to find out where a number would be inserted without actually inserting it? You can use the bisect_left or bisect_right functions:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

This tells us that the number 4 should be inserted at index 2 to keep the list sorted.

Example 3: Maintaining Sorted Order in a Dynamic List

Let’s say you’re managing a dynamically growing list and need to insert elements while ensuring it stays sorted:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

This will output the list at each step as elements are inserted:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Example 4: Using bisect with Custom Objects

Suppose you have a list of custom objects, such as tuples, and you want to insert them based on a specific criterion:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Or you may want to insert based on the second element of each tuple:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect in Action: Searching for Words

The bisect module isn't limited to numbers; it can also be useful for searching in lists of strings, tuples, characters etc.
For instance, to find a word in a sorted list:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Or to find the first word in group of words with a specific prefix:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix + 'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

However, keep in mind that bisect_left returns the index where the target should be inserted, not whether the target exists in the list.

Variants of bisect and insort

The module also includes right-sided variants: bisect_right and insort_right. These functions return the rightmost index at which to insert an element if it’s already in the list. For example, bisect_right will return the index of the first element greater than the target if the target is in the list, while insort_right inserts the element at that position.

bisect Under the Hood

The power of the bisect module lies in its efficient implementation of the binary search algorithm. When you call bisect.bisect_left, for example, the function essentially performs a binary search on the list to determine the correct insertion point for the new element.

Here’s how it works under the hood:

1. Initialization: The function starts with two pointers, lo and hi, which represent the lower and upper bounds of the search range within the list. Initially, lo is set to the start of the list (index 0), and hi is set to the end of the list (index equal to the length of the list). But you can also specify custom lo and hi values to search within a specific range of the list.

2. Bisection: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid + 1`.

1. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort_left code example:

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.