The bisect Module In Python

The bisect module provides functions for finding insertion point for an entry into an already sorted list and for inserting an element into it. The Python examples find the insertion points as well as insert the entries into the already sorted python lists.

Bisect Updated 4 Feb 2020 3 min read

Overview

  • The bisect module is helpful when finding an insertion point or inserting an entry, on an already sorted Python list. The module uses a bisection algorithm.
  • The functions of the bisect module also work, when the value to be inserted is already present in the sorted list. Using an appropriate function - bisect_left() or bisect_right(), an insertion point is found before or after any existing entries with the same value. The bisect() function behaves the same way as the bisect_right() function.
  • A new entry can be inserted into an already sorted Python list through the methods insort_left() or insort_right(). The function insort_right() behaves the same as insort().

Example – Finding an insertion point on a Python list using bisect module

python
# Example Python program that finds the insertion point for

# a new entry into an already sorted Python list

import heapq

import bisect

# A class to represent bags of corn adhering to certain specification

# (quantity, breed and so on)

class CornBag:

    def __init__(self, quantity):

        self.quantity = quantity

    def __eq__(self, anotherObject):

        return self.quantity == anotherObject.quantity

    def __lt__(self, anotherObject):

        return self.quantity < anotherObject.quantity

    def __repr__(self):

        return "%d"%self.quantity

bag1 = CornBag(5)

bag2 = CornBag(5)

bag3 = CornBag(10)

bag4 = CornBag(20)

# Compare corn bags

print("Is bag1 equals to bag2 in specification(i.e.,in quantity)")

print(bag1 == bag2)

print("Is bag1 is bag2:")

print(bag1 is bag2)

# Create a Python list of corn bags

cornbags = [bag1, bag2, bag4, bag3]

print("Corn bags:")

print(cornbags)

heapq.heapify(cornbags)

# Sort the corn bags

print("Corn bags sorted based on quantity:")

ordered = heapq.nsmallest(len(cornbags), cornbags)

print(ordered)

# Find the insertion points for a bag with a quantity of 10 units of corn

pos = bisect.bisect_right(ordered, CornBag(10))

print("The new entry with an already existing value can be inserted to the right of the value at position:")

print(pos)

pos = bisect.bisect(ordered, CornBag(10))

print(pos)

print("The new entry with an already existing value can be inserted to the left of the value at position:")

pos = bisect.bisect_left(ordered, CornBag(10))

print(pos)

Output

Output
Is bag1 equals to bag2 in specification (i.e.,in quantity)

True

Is bag1 is bag2:

False

Corn bags:

[5, 5, 20, 10]

Corn bags sorted based on quantity:

[5, 5, 10, 20]

The new entry with an already existing value can be inserted to the right of the value at position:

3

3

The new entry with an already existing value can be inserted to the left of the value at position:

2

Example: Insert an entry into a sorted list using Bisect Module

python
# Example Python program that inserts a value

# into a sorted list of values using the bisect module

import heapq

import bisect

# Create a Python list of numbers

nums = [2, 8, 6, 4, 14, 12]

# Create a min-heap

heapq.heapify(nums)

# Get a sorted list

sortedList = heapq.nsmallest(len(nums), nums)

print(sortedList)

# Insert new entry into the sorted list

bisect.insort(sortedList, 4)

print(sortedList)

Output

Output
[2, 4, 6, 8, 12, 14]

[2, 4, 4, 6, 8, 12, 14]