Usage of bisect in Python

This article illustrates the use of bisect in Python, which is a common practical technique. Share with you for your reference. Specific analysis is as follows:

In general, bisect in Python is used to manipulate sorted arrays. For example, you can insert data into an array and sort at the same time. The following code demonstrates how to do this:

import bisect
import random
random.seed(1)
print('New pos contents')
print('-----------------')
l=[]
 
for i in range(1,15):
  r=random.randint(1,100)
  position=bisect.bisect(l,r)
  bisect.insort(l,r)
  print '%3d %3d'%(r,position),l

The output result is:

New pos contents
-----------------
 14  0 [14]
 85  1 [14, 85]
 77  1 [14, 77, 85]
 26  1 [14, 26, 77, 85]
 50  2 [14, 26, 50, 77, 85]
 45  2 [14, 26, 45, 50, 77, 85]
 66  4 [14, 26, 45, 50, 66, 77, 85]
 79  6 [14, 26, 45, 50, 66, 77, 79, 85]
 10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77  9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

As you can see, the array is sorted when these random Numbers are inserted. But there are some repeating elements, like 77,77 above. You can set the order of the repeating elements, so if you want the repeating element to appear on the left side of the same element as it does, you use bisect_left, otherwise you use bisect_right, you use insort_left and insort_right. For example, we can see the repeated element index changes in the following code:

import bisect
import random
random.seed(1)
print('New pos contents')
print('-----------------')
l=[]
 
for i in range(1,15):
  r=random.randint(1,100)
  position=bisect.bisect_left(l,r)
  bisect.insort_left(l,r)
  print '%3d %3d'%(r,position),l

The output result is:

New pos contents
-----------------
 14  0 [14]
 85  1 [14, 85]
 77  1 [14, 77, 85]
 26  1 [14, 26, 77, 85]
 50  2 [14, 26, 50, 77, 85]
 45  2 [14, 26, 45, 50, 77, 85]
 66  4 [14, 26, 45, 50, 66, 77, 85]
 79  6 [14, 26, 45, 50, 66, 77, 79, 85]
 10  0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
 3  0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
 84  9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
 44  4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
 77  8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
 1  0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

This function bisect.bisect(list,key) is like the tailMap(fromkey) of TreeMap in Java.

I hope this article has helped you with your Python programming.