Bisect module – Array Bisecting Algorithms in Python

In competitive programming, we often face complexity problems. Many of us get stuck due to the TLE (Time limit exceeded). And a whole lot of it depends on the sorting algorithm used in our code. Here I introduce you to the bisect module in python. Try implementing it in your codes to reduce the complexity.

Bisect Module in Python – Array Bisecting

Bisect is the python module that defines a number of functions to keep the array in a sorted fashion. It automatically inserts the element at the correct position without having to sort the array again every time.  This can be much more efficient than repeatedly sorting a list, or explicitly sorting a large list after the construction. The bisect module implements a binary search. Therefore, O(log n) is its estimated complexity.

Functions in bisect module

Let us discuss in detail each function available to us in bisect module:

1. bisect.bisect(list,item[,low,high]) –

l=[1,4,5,6,7]
print(bisect.bisect(l,3))

>> 1

Now, observe the example above. This function returns the index position of the item when inserted in the list. Keep in mind that it does not modify the list, it simply returns the position. It is assumed that the list is in the sorted manner. Thus, the position returned is according to the correct ascending order. But what happens if the list is not ordered. Let us understand this variation.

l=[5,4,8,1,6]
print(bisect.bisect(l,3))

>> 0
So, we get to know here that bisect functions performs binary search algorithm across the list. It first compares 8 (i.e. the middle number) to 3 (the number to be inserted). Since 8>3 it moves to the left side of the array. It now compares 4 to 3. Since 4 is also greater than 3, it now compares 5 to 3. Eventually, it locates the index 0 for the element 3. Another question arises here is that what position is returned if the element already exists in the given list. In this case, the function simply returns the rightmost position amongst the existing similar elements. An example is given below:

l=[1,3,6,7,7,7,10,20]
print(bisect.bisect(l,7))

>> 6

You may also learn,

• Array Sorting: How to sort an array of integers in Python?
• Duplicate Elements Removal of an Array or List using Python

2.  bisect.bisect_left(list,item [,low,high]) – This function returns the leftmost index position if more than one similar item occurs in the list.

3.  bisect.bisect_right(list,item[,low,high]) – This function is the same as bisect function. It returns the rightmost position in the list.

Let us explore the examples:

l=[12,16,23,45,60]
print(bisect.bisect_left(l,20))
print(bisect.bisect_right(l,20))
l=[12,16,23,23,23,23,45,60]
print(bisect.bisect_left(l,23))
print(bisect.bisect_right(l,23))

>> 2
>> 2
>> 2
>> 6

4.  bisect.insort(list,item[,low,high]) – This is the useful function. It inserts the item in the list at the rightmost index such that the list stays sorted.

5.  bisect.insort_left(list,item[,low,high]) –  This function inserts the element at the leftmost position in the list.

6.  bisect.insort_right(list,item[,low,high]) – This function is similar to insort() function.

Note: insort() functions are analogous to the bisect functions. The difference lies in the fact that bisect() return the index while insort() returns the sorted list.

Snippets of the working program – Array bisect in Python

grades = "FEDCBA"
breakpoints = [30, 44, 66, 75, 85]
from bisect import bisect
def grade(total):
          return grades[bisect(breakpoints, total)]
print(grade(66))
print(map(grade, [33, 99, 77, 44, 12, 88]))

Output:
>> 'C'
>> ['E', 'A', 'B', 'D', 'F', 'A']

#This code outputs the sorted list
import bisect
l=[]
for i in range(5):
    t=int(input())
    bisect.insort(l,t)
print(l)

Input:
3
8
6
1 
4

Output:
>> [1,3,4,6,8]

So, next time you encounter a TLE, just insert the element in the list every time. You do not need to sort the list in each iteration of the loop. Hope, this helped you out. Any suggestions for improvement are always welcome. Enjoy your coding.

Also, learn:

An introduction to classes and objects in python  

For further references, visit the documentation: Documentation python 3.x