Python bisect is explained with an example.

---

The method is based on 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 an 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 the 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 insert the value at the index in another step.

The bisect module has more functions, where in a single step, we can insert a new value at the correct position, following those functions with examples.

insort_left() – 

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

insort_right() –

It finds the position and inserts it right from the value if it is present in the list.

insort()

This is for default insertion. It works similarly 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]