Understanding the bisect() function
The bisect() function is used to find the index where an element should be inserted in a sorted list to maintain its sorted order. It takes two required arguments: the sorted list & the element to be inserted.
For example :
Python
import bisect
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index = bisect.bisect(numbers, 5)
print(index)
You can also try this code with Online Python Compiler
Output
5
In this example, we have a sorted list of numbers & we want to find the index where the number 5 should be inserted. The bisect() function returns the index 5, which means that if we were to insert the number 5 into the list, it would be inserted at index 5 to maintain the list's sorted order.
If the element being searched for is already present in the list, the bisect() function returns the index immediately to the right of the existing element.
For example:
Python
import bisect
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index = bisect.bisect(numbers, 4)
print(index)
You can also try this code with Online Python Compiler
Output
4
In this case, the number 4 is already present in the list, so the bisect() function returns the index 4, which is the index immediately to the right of the existing element.
The bisect() function also accepts optional arguments "lo" & "hi" that allow you to specify the range of indices to search within. By default, "lo" is set to 0 & "hi" is set to the length of the list.
Understanding the bisect_left() function
The bisect_left() function is similar to the bisect() function, but it returns the leftmost index where an element should be inserted in a sorted list if there are duplicate elements in the list.
For example :
Python
import bisect
numbers = [1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
index = bisect.bisect_left(numbers, 4)
print(index)
You can also try this code with Online Python Compiler
Output
3
In this example, we have a sorted list of numbers with duplicate elements (4 appears three times). The bisect_left() function returns the index 3, which is the leftmost index where the number 4 should be inserted to maintain the list's sorted order.
If the element being searched for is not present in the list, the bisect_left() function returns the index where the element should be inserted. For example
Python
import bisect
numbers = [1, 2, 3, 5, 6, 7, 8, 9]
index = bisect.bisect_left(numbers, 4)
print(index)
You can also try this code with Online Python Compiler
Output
3
In this case, the number 4 is not present in the list, so the bisect_left() function returns the index 3, which is the index where the number 4 should be inserted to maintain the list's sorted order.
Like the bisect() function, bisect_left() also accepts optional arguments "lo" & "hi" to specify the range of indices to search within.
The bisect_left() function is useful when you want to find the leftmost insertion point for an element in a sorted list, especially when dealing with lists containing duplicate elements.
Understanding the bisect_right() function:
The bisect_right() function is similar to the bisect() and bisect_left() functions, but it returns the rightmost index where an element should be inserted in a sorted list if there are duplicate elements in the list.
For example :
Python
import bisect
numbers = [1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
index = bisect.bisect_right(numbers, 4)
print(index)
You can also try this code with Online Python Compiler
Output
6
In this example, we have a sorted list of numbers with duplicate elements (4 appears three times). The bisect_right() function returns the index 6, which is the rightmost index where the number 4 should be inserted to maintain the list's sorted order.
If the element being searched for is not present in the list, the bisect_right() function returns the index where the element should be inserted. For example:
Python
import bisect
numbers = [1, 2, 3, 5, 6, 7, 8, 9]
index = bisect.bisect_right(numbers, 4)
print(index)
You can also try this code with Online Python Compiler
Output
3
In this case, the number 4 is not present in the list, so the bisect_right() function returns the index 3, which is the index where the number 4 should be inserted to maintain the list's sorted order.
Like the bisect() and bisect_left() functions, bisect_right() also accepts optional arguments "lo" & "hi" to specify the range of indices to search within.
The bisect_right() function is useful when you want to find the rightmost insertion point for an element in a sorted list, especially when dealing with lists containing duplicate elements.
Understanding the insort() function
The insort() function is used to insert an element into a sorted list while maintaining the list's sorted order. It takes two required arguments: the sorted list & the element to be inserted.
For example :
Python
import bisect
numbers = [1, 2, 3, 5, 6, 7, 8, 9]
bisect.insort(numbers, 4)
print(numbers)
You can also try this code with Online Python Compiler
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]
In this example, we have a sorted list of numbers & we want to insert the number 4 into the list while maintaining its sorted order. The insort() function inserts the number 4 at the appropriate index (which is 3 in this case) & the list remains sorted.
If the element being inserted is already present in the list, the insort() function inserts it to the right of the existing element. For example:
Python
import bisect
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
bisect.insort(numbers, 4)
print(numbers)
You can also try this code with Online Python Compiler
Output
[1, 2, 3, 4, 4, 5, 6, 7, 8, 9]
In this case, the number 4 is already present in the list, so the insort() function inserts another 4 to the right of the existing element.
The insort() function uses the bisect() function internally to find the appropriate index for insertion. It also accepts optional arguments "lo" & "hi" to specify the range of indices to consider for insertion.
Note: The insort() is more efficient than manually searching for the appropriate index & inserting the element using list.insert(), especially for large lists. It maintains the list's sorted order while inserting elements, making it a convenient choice when working with sorted lists.
Understanding the insort_left() function
The insort_left() function is similar to the insort() function, but it inserts the element at the leftmost position in case there are duplicate elements in the sorted list.
For example :
Python
import bisect
numbers = [1, 2, 3, 4, 4, 5, 6, 7, 8, 9]
bisect.insort_left(numbers, 4)
print(numbers)
You can also try this code with Online Python Compiler
Output
[1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
In this example, we have a sorted list of numbers with duplicate elements (4 appears twice). The insort_left() function inserts another 4 at the leftmost position among the existing 4's, maintaining the list's sorted order.
If the element being inserted is not present in the list, the insort_left() function behaves the same as the insort() function & inserts the element at the appropriate index. For example:
Python
import bisect
numbers = [1, 2, 3, 5, 6, 7, 8, 9]
bisect.insort_left(numbers, 4)
print(numbers)
You can also try this code with Online Python Compiler
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]
In this case, the number 4 is not present in the list, so the insort_left() function inserts it at the appropriate index (which is 3) to maintain the list's sorted order.
The insort_left() function uses the bisect_left() function internally to find the appropriate index for insertion. It also accepts optional arguments "lo" & "hi" to specify the range of indices to consider for insertion.
Note: The insort_left() is useful when you want to insert elements into a sorted list & maintain the relative order of duplicate elements, ensuring that the newly inserted element is placed at the leftmost position among the duplicates.
Understanding the insort_right() function
The insort_right() function is similar to the insort() and insort_left() functions, but it inserts the element at the rightmost position in case there are duplicate elements in the sorted list.
For example :
Python
import bisect
numbers = [1, 2, 3, 4, 4, 5, 6, 7, 8, 9]
bisect.insort_right(numbers, 4)
print(numbers)
You can also try this code with Online Python Compiler
Output
[1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
In this example, we have a sorted list of numbers with duplicate elements (4 appears twice). The insort_right() function inserts another 4 at the rightmost position among the existing 4's, maintaining the list's sorted order.
If the element being inserted is not present in the list, the insort_right() function behaves the same as the insort() and insort_left() functions & inserts the element at the appropriate index. For example:
Python
import bisect
numbers = [1, 2, 3, 5, 6, 7, 8, 9]
bisect.insort_right(numbers, 4)
print(numbers)
You can also try this code with Online Python Compiler
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9]
In this case, the number 4 is not present in the list, so the insort_right() function inserts it at the appropriate index (which is 3) to maintain the list's sorted order.
The insort_right() function uses the bisect_right() function internally to find the appropriate index for insertion. It also accepts optional arguments "lo" & "hi" to specify the range of indices to consider for insertion.
Note: The insort_right() is useful when you want to insert elements into a sorted list & maintain the relative order of duplicate elements, which ensures that the newly inserted element is placed at the rightmost position among the duplicates.
Frequently Asked Questions
What is the time complexity of the bisect functions?
The bisect functions have a time complexity of O(log n), making them efficient for searching & inserting elements in sorted lists.
Can the bisect functions be used with custom objects?
Yes, the bisect functions can work with custom objects as long as they are comparable & the list is sorted based on the desired comparison criteria.
Are the bisect functions thread-safe?
The bisect functions themselves are thread-safe, but the underlying list being modified should be protected with locks if accessed concurrently by multiple threads.
Conclusion
In this article, we discussed the Python bisect module & its significant functions for efficiently searching & inserting elements in sorted lists. We learned about the bisect(), bisect_left(), bisect_right(), insort(), insort_left(), & insort_right() functions & saw examples of how they can be used to maintain the sorted order of lists while performing search & insertion operations. The bisect module provides a powerful set of tools for working with sorted lists, offering improved performance compared to linear search & manual insertion techniques.
You can also check out our other blogs on Code360.
117+ registered 