bisect - Add Items to Sorted Array/List Faster¶

Python provides methods for sorting elements of the list. We can keep elements of different types in a list in Python and sort them. Though it does provides a way to sort elements, we need an efficient way to insert elements in the sorted list. The process of adding an element and then sorting the array again each time after adding a new element to the sorted list can be time-consuming. To solve this problem, Python provides us with a module named bisect which helps us find a position to insert an element in a sorted array and insert it. The bisect module uses a basic bisection algorithm to find the best suitable for inserting elements in an array. We'll explain various methods of this module with a simple example as a part of this tutorial.

Example 1¶

As a part of our first example, we'll demonstrate how we can add elements to the sorted array using bisect_left() method.

• bisect_left(a, x, lo=0, hi=len(a)) - It accepts array and element that we want to insert into the array as input and returns an index where we can insert an element in the array. It makes sure for us that the array will still be sorted array after the insertion of the new element. This method will return a left-most index in the array if the element we try to insert is already present one or more times in the array.

Below we have created a simple list and inserting element 7 two times into it. We are then inserting element 12 into the list. We are printing the index returned by bisect_left() method each time to see which position it returns. We can notice that when we first time tried to insert element 7 into the array, it returned index 6 because 7 is already present in the list and this new 7 should be inserted before that 7. When we tried to insert 7 again, it returns index 6 again which will be inserted before already present two entries of 7. When we try to insert elements greater than all elements of the array it returns an index same as the size of the array.

Example 2¶

As a part of our second example, we'll demonstrate how we can use the method bisect_right() to insert an element into the sorted array.

• bisect_right(a, x, lo=0, hi=len(a)) - This method works exactly like bisect_left() with only change that whenever element is already present it returns index which is last after all possible entry of the item we are trying to insert. It returns the right-most index in case of repetition.

Our code for this example is exactly the same as our code for the previous example with the only change that we have used bisect_right() method this time instead. We can notice that when we try to insert 7 two times, it returned a different index each time. The first time it returns index 7 which is after the present entry of 7. The second time it returns index 8 which is after both existing 7 entries.

Example 3¶

As a part of our third example, we'll explain how we can use bisect() method to insert elements into the sorted array. The bisect() method works exactly like bisect_right() method.

Our code for this example is also exactly the same as our previous example with the only change that we are using bisect() method instead. We can notice that our output is exactly the same as our previous example.

Example 4¶

As a part of our fourth example, we are demonstrating how we can directly insert elements into a sorted array using insort_left() method.

• insort_left(a, x, lo=0, hi=len(a)) - This method works exactly like bisect_left() with only change that it actually inserts element at index which would have been returned by bisect_left() method. It inserts element in place.

Our code for this example is also the same as our previous examples where we are inserting elements into an existing sorted array. We are printing the array after each insertion.

Example 5¶

Our fifth example explains how we can insert elements into a sorted array using insort_right() method. The method works exactly like bisect_right() method but instead of returning an index to insert an element, it actually inserts an element into that position.

Our code for this example is like our previous example. It gives the same results as our previous examples.

Example 6¶

Our sixth example explains how we can use insort() method which is exactly like bisect() method but actually inserts items into a sorted array. Our code for this part as well is almost the same as our previous examples.

Example 7¶

As a part of our seventh example, we are using bisect_left() and bisect_right() methods to determine which elements in the sorted array are less than and greater than the given input element. The code for this part is simple and self-explanatory like our previous examples.

Example 8¶

Our eight example demonstrates how we can use methods bisect_left() and bisect_right() methods to find element smaller and bigger than the element supplied as input. If the element is already present in the array then it does not return that element, instead, it returns an element that is exactly bigger or smaller than it. If an element bigger or smaller is not present then it returns None.

This ends our small tutorial explaining how we can use various methods provided by bisect module to insert elements efficiently into a sorted array. Please feel free to let us know your views in the comments section.