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:

# 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:

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:

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

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

# 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:

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

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

The Bisect Module In Python

Overview:

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

Output:

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

Output: