The Python bisect module is a built-in python module that provides functions we can use to maintain a list in sorted order each time we need to insert an item into the list.

With longer lists, it is more efficient for us to use these functions than sorting a list each time we add an item.

However, for the functions in the python bisect module to work properly, each of them requires a sorted list.

In this tutorial, you will learn about the following types of functions provided by the bisect module in python:

  • Functions that find where to insert items in a way that preserves the sort order of a list
  • Functions that insert items in a position that maintains the sort order of a list.

Python bisect functions that search for an insertion point

The bisect module in python has functions that can help us find the index to insert an item in a list, and still preserve the list’s sort order. These functions do not insert the item into the given list. The functions are bisect_left() and bisect_right().

Both functions take two required arguments, in the following order

  • The list to search in. The list has to be sorted
  • The item to be inserted in the list

The return value in both cases is an integer representing the insertion index in the sorted list.

The bisect_left() python bisect function

This function returns the leftmost possible insertion index, without actually inserting the item. If the item occurs in the list, the bisect_left() function returns the index of the leftmost occurrence.


import bisect as bi

# the sorted list
lst = [-4, -1, 9, 13, 13, 14, 20, 23]

# get the insertion index

# 2 is not in the list, but can be inserted in front of 9, so the
# index of 9 will be returned
print(f"2 will be inserted at position {bi.bisect_left(lst, 2)}")

# 14 already exists in the list, so its position is returned
print(f"14 will be inserted at position {bi.bisect_left(lst, 14)}")

# 13 has duplicates, so it will return the index of
# the first occurrence of 13
print(f"13 will be inserted at position {bi.bisect_left(lst, 13)}")

Output:

2 will be inserted at position 2
14 will be inserted at position 5
13 will be inserted at position 3

The bisect_right() python bisect function

This function returns the rightmost possible insertion index without inserting the item into the list. If the item has one or more duplicates of the item in the list, it returns the index after the rightmost, or last, occurrence.


import bisect as bi

# the sorted list
lst = [-4, -1, 9, 13, 13, 14, 20, 23]

# get the insertion index

# 2 is not in the list, but can be inserted after -1, so the
# index after -1 will be returned
print(f"2 will be inserted at position {bi.bisect_right(lst, 2)}")

# 14 already exists in the list, so the position after its position is returned
print(f"14 will be inserted at position {bi.bisect_right(lst, 14)}")

# 13 has duplicates, so it will return the index after
# the last occurence of 13
print(f"13 will be inserted at position {bi.bisect_right(lst, 13)}")

Output:

2 will be inserted at position 2
14 will be inserted at position 6
13 will be inserted at position 5

Note – The python bisect module also contains the function bisect(), which is just an alias for bisect_right().

Insert functions in the python bisect module

The previously discussed functions in the bisect module only searched for the index to insert items without actually inserting them. The python bisect module has functions that actually carry out insertion into lists. After they insert items into the list, the list still remains sorted. The functions are insort_left() and insort_right().

Both functions take two required arguments, in the following order:

  • The list to be modified. The list has to be sorted
  • The item to be inserted

The insort_left() function

This function inserts the item in the leftmost possible index, while still preserving the sort order of the list. If the item already occurs in the list, the function will insert it before the occurrences, or to the left of the first occurrence in the list.


import bisect as bi

def insert_left_routine(item):
# the sorted list to use
lst = [-4, -1, 9, 13, 13, 14, 20, 23]

# display where the item will be inserted
index = bi.bisect_left(lst, item)
print(f"{item} will be inserted at position {index}, in front of {lst[index]}")

# display the original list for reference
print(f"original list for reference: {lst}")

# insert the item
bi.insort_left(lst, item)

# display the modified list
print(f"final list after insertion: {lst}\n\n")

I have included the function insert_left_routine() to help with the demonstration. The function resets the list each time we call it.  This helps us insert an item into a fresh copy of the list. This will help show the changes with respect to the original list.

We will do the actual insertions in the next code segment. There are three cases;

  • we do not have a copy of the item to insert in the list,
  • the item to insert occurs only once in the list,
  • the item to insert exists more than once in the list

# 2 is not in the list; it will be inserted before -1.
insert_left_routine(2)

# 14 already exists in the list; it will be inserted before its occurence
insert_left_routine(14)

# 13 has duplicates; it will be inserted before the first occurrence
insert_left_routine(13)

Output:

2 will be inserted at position 2, in front of 9
original list for reference: [-4, -1, 9, 13, 13, 14, 20, 23]
final list after insertion: [-4, -1, 2, 9, 13, 13, 14, 20, 23]

14 will be inserted at position 5, in front of 14
original list for reference: [-4, -1, 9, 13, 13, 14, 20, 23]
final list after insertion: [-4, -1, 9, 13, 13, 14, 14, 20, 23]

13 will be inserted at position 3, in front of 13
original list for reference: [-4, -1, 9, 13, 13, 14, 20, 23]
final list after insertion: [-4, -1, 9, 13, 13, 13, 14, 20, 23]

The insort_right() function

The insort_right() function inserts the item in the rightmost possible position in the list without affecting the sort order of the list. If the item already exists in the list, it inserts the item immediately after the last occurrence.


import bisect as bi

def insert_right_routine(item):
# the sorted list
lst = [-4, -1, 9, 13, 13, 14, 20, 23]

# display where the item will be inserted
index = bi.bisect_right(lst, item)
print(f"{item} will be inserted at position {index}, after {lst[index]}")

# display the original list for reference
print(f"original list for reference: {lst}")

# insert the item
bi.insort_right(lst, item)

# display the modified list
print(f"final list after insertion: {lst}\n\n")

This example makes use of the function insert_right_routine(). It has a similar function to the
insert_left_routine() in the previous example. It allows us to use a fresh copy of the list when we want to insert a new item into the list.

Here too, like the example for insort_left(), the items to be inserted will have three cases;

  • the item to insert does not exist in the list,
  • only one instance of the item to insert exists in the list, and
  • more than one instance of the item to insert exists in the list.

The next code segment shows these three cases and their output


# 2 is not in the list; it will be inserted after -1.
insert_right_routine(2)

# 14 already exists in the list; it will be inserted after its occurrence
insert_right_routine(14)

# 13 has duplicates; it will be inserted after the last occurrence
insert_right_routine(13)

Output:

2 can be inserted at position 2, after 9
original list for reference: [-4, -1, 9, 13, 13, 14, 20, 23]
final list after insertion: [-4, -1, 2, 9, 13, 13, 14, 20, 23]

14 can be inserted at position 6, after 20
original list for reference: [-4, -1, 9, 13, 13, 14, 20, 23]
final list after insertion: [-4, -1, 9, 13, 13, 14, 14, 20, 23]

13 can be inserted at position 5, after 14
original list for reference: [-4, -1, 9, 13, 13, 14, 20, 23]
final list after insertion: [-4, -1, 9, 13, 13, 13, 14, 20, 23]

Note – The bisect module also contains the function insort(), which is an alias for insort_right().

Conclusion

This ends our brief tutorial. We hope this tutorial was helpful in introducing you to the bisect module in Python.

If you are in a need of any python help or looking for someone who can help with python then feel free to drop us a message.