Python

How to Use Bisect Module in Python

This article will cover a guide on using the “Bisect” module available in standard Python built-in libraries. Bisect module can be used to run a variety of operations on list type iterable objects available in Python. All code samples in this article are tested with Python 3.9.5 on Ubuntu 21.04.

About Bisect Module

The bisect module allows you to call various methods on a Python list and helps you keep the list sorted. It is especially useful if you want to modify elements of a list but at the same time keep its order. For instance, if you want to insert an element in a list, the bisect method will return an index where a new element can be inserted in such a way that after insertion, the list will remain sorted. The syntax for Bisect methods can be best understood through examples, some of them are covered below:

Inserting an Element into a List Using the Bisect Method

Take a look at the code sample below:

import bisect

l = [2, 1, 3, 5]
l.sort()
i = bisect.bisect(l, 4)
print (i)
l.insert(i, 4)
print (l)

The first statement imports the “bisect” module. Next a list type object “l” is defined. In the next statement, the list is sorted by calling the “sort” method on it. The bisect method is called upon the list on the next line. The bisect method takes two arguments, the list it wants to bisect and the element that needs to be inserted in the list while keeping the sort order. In this case, the method bisect is called upon to determine at what index number “4” should be inserted in list “l” so that everything is kept in order after insertion. The variable “i” keeps the values of the index returned by the bisect method. Finally, the number 4 is inserted in the list “l” at index “i” by calling upon the “insert” method on the list.

After running the above code sample, you should get the following output:

3
[1, 2, 3, 4, 5]

Number “3” is the index in the original list where number 4 has been inserted. List indexes always start with zero, hence number 4 has been inserted at the 4th position.

Note that If a number already exists in the list, the bisect method finds an index to the right of the existing number. Take a look at the code sample below:

import bisect

l = [2, 1, 3, 5, 4]
l.sort()
i = bisect.bisect(l, 4)
print (i)
l.insert(i, 4)
print (l)

After running the above code sample, you should get the following output:

4
[1, 2, 3, 4, 4, 5]

The bisect module includes another method called “bisect_right” which is identical to the “bisect” method. You can use these methods interchangeably.

Inserting an Element into a List from Left Using the Bisect Method

Consider the code sample below:

import bisect

l = [2, 1, 3, 5, 4, 4]
l.sort()
i = bisect.bisect_left(l, 4)
print (i)
l.insert(i, 4)
print (l)

It is almost the same as the previous example, except that instead of the bisect method, “bisect_left” is now used. In case of an existing element, the bisect_left method finds the leftmost index. You can use this index to add a new element to the left of a matched element.

After running the above code sample, you should get the following output:

3
[1, 2, 3, 4, 4, 4, 5]

The number 4 is added at index 3, that is, at 4th position in the list since the index always starts with zero. If you use the bisect or bisect_right method instead, the returned index will be different. Take a look at the code sample below:

import bisect

l = [2, 1, 3, 5, 4, 4]
l.sort()
i = bisect.bisect_right(l, 4)
print (i)
l.insert(i, 4)
print (l)

After running the above code sample, you should get the following output:

5
[1, 2, 3, 4, 4, 4, 5]

Using the Insort Method

The bisect module also provides “insort” and “insort_left” methods that can be used to directly insert elements into a list at appropriate positions. You can also use the “insort_right” method in place of isnort method. Take a look at the code sample below:

import bisect

l = [2, 1, 3, 5, 4, 4]
l.sort()
bisect.insort(l, 4)
print (l)

The code sample is very similar to earlier examples. The insort method takes two arguments: the list to be modified and the element to be inserted at the appropriate position. There is no need to call upon the “insert” method on the list to manually insert the element in the list at the matched index.

After running the above code sample, you should get the following output:

[1, 2, 3, 4, 4, 4, 5]

The insort method is just a convenience method which is equivalent to the following Python statement (assuming “l” is a sorted list):

l.insert(bisect.bisect(l, 4), 4)

So under the hood, insort follows the same rules as the bisect, bisect_right, and bisect_left methods.

Conclusion

As the bisect module provides methods to modify a list by inserting elements in it while keeping the sort order, a lot of repetitive code is removed where you may have to constantly sort a list after making modifications to it. According to the official Python docs, bisect method provides improvements over other commonly used approaches, especially when a list has a large number of elements.

About the author

Nitesh Kumar

I am a freelancer software developer and content writer who loves Linux, open source software and the free software community.