Python Bisect | Working With Python Bisect Module

Python bisect module comes handy when we need to insert new data while maintaining the data in sorted order. Without this module, it would have been a real pain for our systems’ processor. Our data remains sorted when a new insertion is made. The only thing we have to keep in mind is that the data is already in sorted order.

Let us learn about some the use cases of Python bisect and why it is so useful in real life.

Contents

Importing Python bisect module –

Python bisect module comes preinstalled with python, and we need to import it before using it. The only prerequisite for using this module is that the data structure should already be sorted. Otherwise it would not give correct answers.

To import this module, use –

import bisect

Various functions in python bisect module

There is a total of 6 functions available in this module, each having its applications. Let’s learn each of them.

Bisect (a, x[, lo[, hi]])

This function, when used, returns the index at which you should insert the given element in the given list, keeping the list sorted.

The first argument is the list where you want to make the insertion, x is the element we want to insert. Lo and hi are the starting and ending index of the list you want to consider. If we do not pass the values in the last two parameters, the whole list would be considered. These functions can be used on both the numeric list and the list containing the names.

Suppose we have a list containing the marks in the sorted order from highest to lowest. And we want to enter new marks in the same list containing the list sorted.

marks=[33,36,40,43,44,48,50] 
new_marks=42 
print(bisect.bisect(marks,new_marks))

Output- 
3

Note- Remember that the index of the list starts from index 0.

bisect_left(a, x[, lo[, hi]])

Suppose that the element you want to insert is already present in the list, bisect_left() returns the index before that element. Let us look at an example to understand it better.

marks=[33,36,40,42,43,44,48,50]
new_marks=42 
bisect.bisect_left(marks,new_marks)

Output- 
3

bisect_right(a, x[, lo[, hi]])

Unlike the bisect_left() function, if the element is already present, this function returns the index after that element.

marks=[33,36,40,42,43,44,48,50] 
new_marks=42 
bisect.bisect_right(marks,new_marks)

Output- 
4

Note that the bisect() function works same as bisect_right() and is just a shorthand for bisect_right().

The time complexity of these functions is O(log(n)), as it is based on the concept of binary search.

insort(a, x[, lo[, hi]])

This function is used to insert the element in the list without disturbing the order of the list. Other things like parameters are precisely the same as bisect().

numbers=[1,2,5,7,11,13,19] 
new_element=17 
bisect.insort(numbers,new_element) 
print(numbers)

Output-
[1, 2, 5, 7, 11, 13, 17, 19]

insort_left()

It is similar to bisect_left(). The insertion takes place before the already present element.

numbers=[1,2,5,7,11,13,17,19] 
new_element=17 
bisect.insort(numbers,new_element) 
print(numbers)

Output-
[1, 2, 5, 7, 11, 13, 17, 19]

Insort_right()-

It works same as insort().

Note- The time complexity of insort() is O(n).

Now that we have learned about these functions let us try to search for the index without using the python bisect module.

Program to find the index without python bisect module-

Let’s make a program working the same as python bisect.bisect().

numbers=[10,12,14,17,19.2,22,23] 
x=17 
for i in range(len(numbers)): 
    if numbers[i] < x: 
       pass 
   #For bisect.left() remove the below elif statement 
    elif numbers[i] == x: 
       pass 
   else: 
       print(i) 
       break

Output
4

This much of code we have to write when we want to search for index without using the bisect(). Also, this program takes much more time to implement than bisect() when we have lots and lots of data.

Now let’s program for insort()-

numbers=[10,12,14,17,19.2,22,23] 
x=17 
for i in range(len(numbers)): 
    if numbers[i] < x: 
       pass 
   #For insort.left() remove the below elif statement 
    elif numbers[i] == x: 
       pass 
   else: 
       numbers[i]=x 
       break

Output-
[10,12,14,17,17,19.2,22,23]

Now you can think about how easy the python bisect module makes it for us.

Some More Examples-

Let us see how can bisect() help us in strings-

Suppose you have a list of student names in sorted order. Now, a new student named ‘Manish’ takes admission. Now let us see how we can add his name keeping the list sorted.

names=['Ashwini','Bulbul','Chetan','Naman','Zubair'] 
new='Manish' 
bisect.insort(names,new) 
print(names)

Output-
['Ashwini', 'Bulbul', 'Chetan', 'Manish', 'Naman', 'Zubair']

Let, suppose we want to add a list of marks in our marks list.

marks=[21,30,31,33,36,40,43,44,48,50]  
newlist=[32,48,29] 
for i in newlist: 
    bisect.insort(marks,i) 
print(marks)

Output-
[21, 29, 30, 31, 32, 33, 36, 40, 43, 44, 48, 48, 50]

Limitations of Python Bisect()-

We need elements in sorted order. To solve this problem, we can use the python sort() function.

marks=[21,30,43,12,29,50,48]  
marks.sort() 
newlist=[32,48,29] 
for i in newlist: 
    bisect.insort(marks,i) 
print(marks)

Output-
[12,21,29,29,30,32,43,48,48,50]

If the list is in descending order, we first need to convert it to ascending order.

marks=[50,49,48,47,46] 
marks.sort() 
newlist=[32,48,29] 
for i in newlist: 
    bisect.insort(marks,i) 
print(marks[::-1])

Output-
[50, 49, 48, 48, 47, 46, 32, 29]

Must Read:

Conclusion

As we have seen there are multiple use cases of the python bisect module. If it was not there we will have to write lots and lots of code and also it would have caused a lot of strain on our processors.

Try to run the programs on your side and let me know if you have any queries.

Happy Coding!