Function Name
bisect_left
Function Signature
bisect_left(pythonList, newElement, lo=0, hi=len(a));
Parameters
pythonList – The Python list whose elements are in sorted order.
newElement – The new element for which the position is to be found in the already sorted Python list.
lo – The lowest position of the search interval to be used as a heuristic.
hi – The highest position of the search interval to used as a heuristic.
Return Value
The position at which the element can be inserted into the Python list while maintaining the sorted order of the list.
Method Overview
- The bisect_left() function finds and returns the position at which an element can be inserted into a Python list while maintaining the sorted order of the Python list. If the list already has elements with the same value as the new element, the insertion point is to the left of first such element.
- The position returned by the bisect_left() can be used as the parameter to the list.insert() to get the new element inserted into the list.
Example
# Example Python program that finds the insertion
# point of an element on an already sorted list
import heapq
import bisect
# class definition for a Currency Note
class CurrencyNote:
def __init__(self, value):
self.value = value
def __eq__(self, anotherNote):
return self.value == anotherNote.value
def __lt__(self, anotherNote):
return self.value < anotherNote.value
def __repr__(self):
return "A %d dollar note"%self.value
# Currency note objects of various sovereign values
c1 = CurrencyNote(1)
c2 = CurrencyNote(10)
c3 = CurrencyNote(20)
c4 = CurrencyNote(50)
c5 = CurrencyNote(100)
# A Python list as wallet
wallet = [c2, c3, c1, c4, c5]
# Show wallet contents
print(wallet)
# Create a min heap
heapq.heapify(wallet)
# Sort the wallet
sortedWallet = heapq.nsmallest(len(wallet), wallet)
# Show the sorted wallet
for note in sortedWallet:
print(id(note))
# Find the insertion point ( to the left of an existing element, if the element exists)
newNote = CurrencyNote(20)
print("Id of the new note is: %s"%id(newNote))
insertionPoint = bisect.bisect_left(sortedWallet, newNote)
print("Position of the newly inserted note in the wallet:")
print(insertionPoint)
# Insert the element
sortedWallet.insert(insertionPoint, newNote)
# Show the sorted wallet with the new note inserted
for note in sortedWallet:
print(id(note))Output
[A 10 dollar note, A 20 dollar note, A 1 dollar note, A 50 dollar note, A 100 dollar note]
4320544848
4320544176
4321526112
4321526304
4321526448
Id of the new note is: 4321527696
Position of the newly inserted note in the wallet:
2
4320544848
4320544176
4321527696
4321526112
4321526304
4321526448