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.
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.
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]
Your privacy choices
We'd like to use Google Analytics cookies to count visits and see which tutorials are useful.
They are only set if you accept. We don't use advertising cookies and we don't sell your data.
You can change your choice any time from “Your privacy choices” at the bottom of every page.
Privacy Policy
Your privacy choices
Your browser sent a Global Privacy Control signal, so analytics is off unless you turn it on here.
Strictly necessary
Remembers this choice in your browser. No cookies, nothing sent to anyone.Always on