bisect_left function of bisect module in python

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: