bisect_right function of bisect module in python

Function Name:

bisect_right

Function Signature:

bisect_right(list, newElement, lo, hi=len(list))

Parameters:

list – The already sorted list in which the insertion point is to be found, which will maintain the sorted order. If the list already contains one or more values as the new value, the insertion position is to the right of the last such occurrence.

newElement – The new element for which the insertion point is to be found.

lo - The lowest position of the search interval to be used as a heuristic. The default value is 0.

hi - The highest position of the search interval to be used as a heuristic. The default value is the number of elements present in the list.

Return Value:

Returns the insertion point of the new element that will maintain the sorted order of the Python list.

Overview:

The bisect_right() function returns the position on which a new element can be inserted into an already sorted Python list, while maintaining the sorted order.
If there are one or more elements present with the same value as the new value then the insertion point is past the right side of the last such element.
The position returned can be used as the first parameter to the list.insert() method of the Python list class.

Example:

# Example Python program that finds the insertion

# point for an element, in an already sorted Python list

import bisect

import heapq

# Class representing a share in a company.

# This specific implementation assumes there could be

# shares of various face value(In reality two face values are common)

class Share:

def __init__(self, companyName, faceValue):

self.companyName = companyName

self.faceValue = faceValue

def __eq__(self, share):

return (self.companyName == share.companyName) and (self.faceValue == share.faceValue)

def __lt__(self, share):

return self.faceValue < share.faceValue

def __repr__(self):

return "1 share of %s with face value:$%.2f"%(self.companyName, self.faceValue)

# Create shares

s1 = Share("Example Company", 1)

s2 = Share("Example Company", 5)

s3 = Share("Example Company", 10)

s4 = Share("Example Company", 15)

s5 = Share("Example Company", 20)

# A list of shares of various classes

shares = [s2, s4, s1, s3, s5]

print("List before sorting:")

print(shares)

# Sort the shares

heapq.heapify(shares)

sortedShares = heapq.nsmallest(len(shares), shares)

print("Sorted list before inserting the new element:")

for share in sortedShares:

print(id(share))

# Create another share with face value of 15

s6 = Share("Example Company", 15)

print("Id of new element (s6):%s"%id(s6))

# Find the insertion point for s6

pos = bisect.bisect_right(sortedShares, s6)

# Insert s6 into sortedShares at the right position

sortedShares.insert(pos, s6)

# Print the list of shares after insertion of s6

print("Sorted list after inserting the new element:")

for share in sortedShares:

print(id(share))

Output:

List before sorting:

[1 share of Example Company with face value:$5.00, 1 share of Example Company with face value:$15.00, 1 share of Example Company with face value:$1.00, 1 share of Example Company with face value:$10.00, 1 share of Example Company with face value:$20.00]

Sorted list before inserting the new element:

4320502840

4320503008

4320503120

4320503176

4320503064

Id of new element (s6):4320503232

Sorted list after inserting the new element: