Bisect Algorithm Functions in Python

Python Methods and Functions

Python provides bisect algorithms in its definition using the " bisect " module, which allows the list to be saved in sorted order after each element is inserted. This is important as it shortens the time it takes to sort the list over and over after inserting each item.

Important bisectional functions

1. bisect (list, num, beg, end) : — This function returns the position in the sorted list, where you can put the number passed in the argument to keep the resulting list in sorted order . If the element is already in the list, the right-most position where the element should be inserted is returned.  This function takes 4 arguments: the list to work with, the number to insert, the starting position in the list to look at, the ending position to look at .

2. bisect_left (list, num, beg, end) : — this function returns the position in a sorted list, where the number passed in the argument can be placed to keep the resulting list in sorted order . If the element is already in the list, the left-most position where the element should be inserted is returned.  This function takes 4 arguments: the list to work with, the number to insert, the starting position in the list to look at, the ending position to look at .

3. bisect_right (list, num, beg, end) : — this function works similarly to " bisect () " mentioned above.

# Python code to demonstrate how it works
# bisect (), bisect_left () and bisect_right ()

 
# import in half for halving

import bisect

 
# initializing list

li = [ 1 , 3 , 4 , 4 , 4 , 6 , 7 ]

  
# using bisect () to find the index to insert new element
# returns 5 (right highest possible index)

print ( "The rightmost index to insert, so list remains sorted is :" , end = "")

print (bisect.bisect (li, 4 ))

 
# using bisect_left () to find the index to insert a new element
# returns 2 (left highest possible index)

print ( "The leftmost index to insert, so list remains sorted is :" , end = "")

print (bisect. bisect_left (li, 4 ))

 
# using bisect_right () to find the index to insert the new element
# returns 4 (right highest possible index)

print ( "The rightmost index to insert, so list remains sorted is :" , end = "")

print (bisect.bisect_right (li, 4 , 0 , 4 ))

Output:

 The rightmost index to insert, so list remains sorted is: 5 The leftmost index to insert, so list remains sorted is: 2 The rightmost index to insert, so list remai ns sorted is: 4 

4. insort (list, num, beg, end) : — This function returns a sorted list after inserting a number at the appropriate position , if the item is already in the list, the item is inserted at the rightmost position. This function takes 4 arguments: list to work with, number to insert, starting position in the list to look at, ending position to look at .

5. insort_left (list, num, beg, end) : — This function returns a sorted list after inserting a number at the appropriate position , if the item is already in the list, the item is inserted at the leftmost possible position. This function takes 4 arguments: list to work with, number to insert, starting position in the list to look at, ending position to look at .

6. insort_right (list, num, beg, end) : — this function works similarly to "insort ()" as mentioned above.

# Python code to demonstrate how it works
# insort (), insort_left () and insort_right ()

 
# import in half" for halving

import bisect

 
# initializing list

li1 = [ 1 , 3 , 4 , 4 , 4 , 6 , 7 ]

  
# initializing list

li2 = [ 1 , 3 < code class = "plain">, 4 , 4 , 4 , 6 , 7 ]

 
# initializing list

li3 = [ 1 , 3 , 4 , 4 , 4 , 6 , 7 ]

 
# use Using insort () to insert 5 at the appropriate position
# insert at 6th position

bisect.insort (li1, 5 )

  

print ( " The list after inserting new element using insort () is: " )

for i in range ( 0 , 7 ) :

print (li1 [i ], end = "" )

 
# using insort_left () to insert 5 at the appropriate position
# insert at 6th position

bisect.insort_left (li2, 5 )

 

print ( " " )

  

print ( "The list after inserting new element using insort_left () is: " )

for i in range ( 0 , 7 ):

  print (li2 [i], end = "" )

 

print ( "" )

 
# using insort_right () to insert 5 at the appropriate position
# insert at 5th position

bisect.insort_right ( li3, 5 , 0 , 4 )

  

print ( "The list after inserting new element using insort_right () is: " )

for i in range ( 0 , 7 ):

print (li3 [i], end = "" )

Output:

 The list after inserting new element using insort () is: 1 3 4 4 4 5 6 The list after inserting new element using insort_left () is: 1 3 4 4 4 5 6 The list after inserting new element using insort_right () is: 1 3 4 4 5 4 6 

by Manjit Singh . If you are as Python.Engineering and would like to contribute, you can also write an article using contribute.python.engineering or by posting an article contribute @ python.engineering. See my article appearing on the Python.Engineering homepage and help other geeks.

Please post comments if you find anything wrong or if you would like to share more information on the topic discussed above.





Tutorials