python bisect example

Python bisect methods | How to use with an example.


The method is based upon the binary search tree (BST) algorithm. In a BST, all the values in the left subtree are smaller than the root value and in the right subtree, all values are greater than or equal to the root values.

Being all the time sorted, a binary search tree concept is a preferred choice for inserting and searching a value with a  complexity O(log n).  Where n is the total number of elements in the list.

The bisect module in Python works over a list. It provides necessary methods so that a list remains sorted after each insertion.  To do that, we have methods to check the position of a new element and then insert the element at that position.

Following is the description of all methods of the module. 

bisect_left() – 

This function returns the position (as integer index) in the sorted list where the new element can be inserted. If the list already contains the value, the function returns the position just left to the existing value else returns an index where all left values are shorter and all right values are greater than the new element. 

bisect_right() – 

Similar to the above returns right next position if the list already contains the value.

 #Python program to demonstrate the use of bisect module
 import bisect;
 #initializing a list with values in random order
 myList = [34,5,6,6,7,3,4,5,10,388,200];
 #First sort the list;
 myList.sort();
 print(myList);
 value = 6;
 index = bisect.bisect_left(myList,value);
 print(" Index for value 6 from bisect_left = " , index);
 index = bisect.bisect_right(myList,value);
 print(" Index for value 6 from bisect_right = " , index);
 #code for insertion in list at given index
 myList.insert(index,value);
 print("New List = ", myList);

Output->

  [3, 4, 5, 5, 6, 6, 7, 10, 34, 200, 388]
  Index for value 6 from bisect_left =  4
  Index for value 6 from bisect_right =  6
 New List =  [3, 4, 5, 5, 6, 6, 6, 7, 10, 34, 200, 388]

In the above code, the insertion was done in two steps. The first step is to find the location for a new value and in another step, insert the value at the index.

The bisect module has more functions, wherein a single step we can insert a new value at correct potions. Following those functions with example.

insort_left() – 

It finds the position and inserts left to the value if it is present in the list.

insort_right() –

It finds the position and inserts left to the value if it is present in the list.

insort()

This is for default insertion. It works similar to insort_right().

Python program to demonstrate the use of bisect module
 import bisect;
 initializing a list with values in random order
 myList = [34,5,6,6,7,3,4,5,10,388,200];
 First sort the list;
 myList.sort();
 print(myList);
 value = 6;
 bisect.insort_left(myList, value);
 print("New List = ", myList);
 bisect.insort_right(myList, value);
 print("New List = ", myList);
 bisect.insort(myList, value);
 print("New List = ", myList);

Output->

 [3, 4, 5, 5, 6, 6, 7, 10, 34, 200, 388]
 New List =  [3, 4, 5, 5, 6, 6, 6, 7, 10, 34, 200, 388]
 New List =  [3, 4, 5, 5, 6, 6, 6, 6, 7, 10, 34, 200, 388]
 New List =  [3, 4, 5, 5, 6, 6, 6, 6, 6, 7, 10, 34, 200, 388]