The bisect module in the standard library provides essential functions for maintaining sorted lists. The various functions provided by the module allow us to perform list operations such as insertions and deletions while ensuring that the list remains in a sorted state. In practice, this is usually much more efficient than repeatedly sorting the list after various operations.

The module provides two basic functions: bisect() and insort(). The bisect() functions finds the position at which an item should be inserted to maintain the list's sorted state, while insort() actually performs the insertion. Both functions assumes that the input list is already sorted.

ExampleEdit & Run

Use the bisect function to get the index

import bisect

L = [1, 2, 3, 4, 6, 7]

#at which index should a value be placed?
print(bisect.bisect(L, 0))
print(bisect.bisect(L, 5)) 
 Visualize 
copy
Output:
0
4
[Finished in 0.012666406109929085s]
ExampleEdit & Run

Perform the actual insertion

import bisect

L = [1, 2, 3, 4, 6, 7]

bisect.insort(L, 0)
bisect.insort(L, 5)
bisect.insort(L, 8)

print(L)
 Visualize 
copy
Output:
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[Finished in 0.013555163983255625s]

The insort() function also allows us to specify a key function which it will use to determine the sorting criteria of the input list.

ExampleEdit & Run

Use the insort() function with a key

import bisect

#elements sorted with their absolute value
L = [1, -2, 3, -4, 6, -7]

#Spesfy the builtin abs() function as the key
bisect.insort(L, 0, key = abs)
bisect.insort(L, -5, key = abs)
bisect.insort(L, -10, key = abs)

print(L)
 Visualize 
copy
Output:
[0, 1, -2, 3, -4, -5, 6, -7, -10]
[Finished in 0.012239508796483278s]

The following example uses the random module to generate random numbers, the bisect insort() function inserts the numbers in a list in a desceding order.

ExampleEdit & Run
import bisect
import random

L = []

for i in range(10):
    bisect.insort(L, random.randint(0, 100), key = lambda x: -x)

print(L)
 Visualize 
copy

 

Output:
[85, 84, 81, 80, 79, 72, 71, 68, 42, 26]
[Finished in 0.014141740277409554s]

functions defined in the bisect module

The functions defined in the module are as summarized below.

function description
bisect(a, x, lo=0, hi=None, key = None) Finds the index in the list a where x should be inserted to maintain the sorted state of the list.
bisect_left(a, x, lo= None, key = None ) Just similar to the bisect() function in that it returns the index  where x. should be inserted to maintain the sorted state. If x appears in the list it returns the index just before the leftmost value of x already in the list.
bisect_right(a, x, lo = 0, hi = None, key = None) Returns the index  where x. should be inserted to maintain the sorted state. If x appears in the list it returns the index just after the rightmost most value of x already in the list.
insort(a, x, lo = 0, hi = None, key = None) Inserts x in the list a while preserving the sorted state of the list.
insort_left(a, x, lo = 0, hi = None, key = None) Uses the bisect_left() function to get the index where to insert element x in list a.
insort_right(a, x, lo = 0, hi = None, key = None) Uses the bisect_right() function to get the index where to insert element x in list a.

The lo and hi parameters in bisect functions refers to the  starting and ending indices , respectively. If specified the operation will only happen within the range specified by these indices.