When you have a sorted list and you wish to insert an element to the list without altering its sorted order. The native approach is to insert the new element at the end of the list, then sort the list again. This may be a non-issue for small projects but it can get computationally expensive when you have a bigger project with extremely long lists. You thus need to find an efficient way to search and insert elements in a sorted list. The python bisect module helps you do this. You can insert an element in a sorted list without needing to sort the list all over again.
The process of element insertion in a sorted list can be split into two steps. The first is to find the position where the element would be inserted. Consequently, the actual insertion takes place. In this tutorial, you will learn how to use the bisect functions to do these two operations with a lot of flexibility. You will learn about the Python bisect function, bisect_left function, and the bisect_right function. Furthermore, you will understand how to use the insort function, insort_left function, and the insort_right function.
We will corroborate our explanations with examples. It is believed that the python bisect examples would help solidify your understanding of how to use the python bisect algorithm.
Let’s get started.
Table of Contents
1. Python bisect function
The python bisect function finds the location of insertion of an element in a sorted list and returns its rightmost index such that the list remains sorted. Say I want to bisect 2 in a list such as [0, 1, 2, 2, 3], the rightmost occurrence of 2 is at index 3. So the bisect function returns the next index, which is 4.
Note that the bisect function does not return the list, it rather returns the index where the insertion would have taken place. According the official documentation, the bisect function takes 4 arguments but 2 required arguments, bisect(a, x, lo=0, hi=len(a)). The ‘a’ parameter is a sorted list while the ‘x’ parameter is the element to be inserted. Lo and hi are the span of the list to be regarded.
If you wish to consider a part of the list, you can specify the lo and hi. By default, the bisect function considers the entire list. Let’s see an example.
#import the bisect library
import bisect
#define a list of sorted numbers
list_1 = [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
#pass the list and element (3) as argument to the bisect function and print the result
print('The rightmost index to insert the element into the sorted index is:', end=' ')
print(bisect.bisect(list_1, 3))
Output:
The rightmost index to insert the element into the sorted index is: 5
Let’s see what happened under the hood. As mentioned earlier, the bisect function parses the list and returns the rightmost index for which the element will be inserted without altering the arrangement.
The defined list was [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]. Python counts from 0 so the first element (which is 1) is of index 0 and the second 1 has index 1. The two 2’s count as index 2 and 3 while 3 counts as index 4. Since we pass 3 as the number to be bisected, the iteration stops and returns the next index, which is 5.
If you wish to return the leftmost index rather than the right, you can use the bisect_left method. Let’s take a look at it next.
2. Python bisect_left function.
The bisect_left function works like the bisect function. Only that this time, as the name suggests, it returns the leftmost index. Let’s see an example.
#define a list of sorted numbers
list_1 = [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
#pass the list and element (3) as argument to the bisect_left function and print the result
print('The leftmost index to insert the element into the sorted index is:', end=' ')
print(bisect.bisect_left(list_1, 3))
Output:
The leftmost index to insert the element into the sorted index is: 4
Notice now that it returns 4. This is because it returns the index before 3. If we add as many 3s to the list, it would still return 4. That’s because the bisect_left does not care about how many times the number occurs. It just returns the index before the first occurrence of that number.
3. Python bisect_right function
There is also a bisect_right function. It however works like the bisect function described earlier. If you do not believe me, let’s run the same example we ran the last time. This time, with the bisect_right function.
#define a list of sorted numbers
list_1 = [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
#pass the list and element (3) as argument to the bisect function and print the result
print('The rightmost index to insert the element into the sorted index is:', end=' ')
print(bisect.bisect_right(list_1, 3))
Output:
The rightmost index to insert the element into the sorted index is: 5It returns index 5 as expected.
4. The insort function
The insort function is the second step that does the real insertion process. The function returns the list after the element has been inserted in the rightmost index without altering the sorted order. Just like its bisect counterpart, the insort function takes 4 arguments but 2 required ones – the list we desire to insert and the element to be inserted. Let’s see how this is done with a coding example.
#define a list of sorted numbers
list_1 = [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
#pass the list and element (3) as argument to the insort function and print the result
bisect.insort(list_1, 3)
# print the list
print(list_1)
Output:
[1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6]As seen, the number 3 which appeared once in the defined list now appears twice in the returned list.The insort function inserts 3 into the list by the insort function.
5. The insort_left function
The insort_left function returns the list after the element has been inserted in the left_most index without altering the sorted list order. Let’s try an example.
#define a list of sorted numbers
list_1 = [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
#insort 1 to the list
bisect.insort_left(list_1, 1)
# print the list
print(list_1)
Output:
[1, 1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
Now, 1 appears thrice. Believe it or not, the inserted 1 is at index 0.
6. The insort_right function
The insort_right acts like the insort function as it also inserts the element in the rightmost index of the sorted list and returns the list. Let’s attempt to insert 6 into the list.
#define a list of sorted numbers
list_1 = [1, 1, 2, 2, 3, 4, 5, 5, 5, 6]
#insort_left 6 to the list
bisect.insort_right(list_1, 6)
# print the list
print(list_1)
Output:
[1, 1, 2, 2, 3, 4, 5, 5, 5, 6, 6]
This time, the inserted 6 is the last element in the list.
In conclusion, you have seen how to carry out a quick binary search of sorted lists using the python bisect function. You also discovered how to insert elements in a sorted list with the insort function.