Last Updated on 2024-10-27 by Clay
bisect is a built-in Python module, primarily designed to maintain the order of a sorted list, allowing items to be inserted without the need to re-sort the entire list.
Many developers might have experienced the following scenario when working on coding tasks or implementing certain functionalities:
When we want to maintain the order of numbers in an array while constantly adding new elements, a common, albeit inefficient, approach is to re-sort the array each time we insert a new value.
In larger arrays, this re-sorting approach is computationally heavy. The bisect module is built to optimize this need using a bisection-based algorithm.
Using bisect
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
Parameter meanings are as follows:
ais a sorted arrayxis the value to insertlois the starting point for evaluation, with a default of 0hiis the endpoint for evaluation, defaulting to the length of the arraykeyis a comparison method, added in Python 3.10, which allows you to define a key function for custom comparisons. If None, values are compared directly by their size
Here’s a code example:
# coding: utf-8
import bisect
def main() -> None:
arr = [1, 2, 5, 5, 6, 8]
insert_val = 3
print(bisect.bisect_left(arr, insert_val))
if __name__ == "__main__":
main()
Output:
2
In the array [1, 2, 5, 5, 6, 8], inserting the value 3 correctly at index 2 keeps the array sorted.
There’s also another function, bisect_right(). What’s the difference between bisect_left() and bisect_right()?
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
Functionally, these two methods are nearly identical. The key difference lies in which insertion point is returned: one returns the leftmost possible index, while the other returns the rightmost possible index.
This distinction is clearer in code:
# coding: utf-8
import bisect
def main() -> None:
arr = [1, 2, 5, 5, 6, 8]
insert_val = 5
print(f"bisect_left(): {bisect.bisect_left(arr, insert_val)}")
print(f"bisect_right(): {bisect.bisect_right(arr, insert_val)}")
if __name__ == "__main__":
main()
Output:
bisect_left(): 2
bisect_right(): 4
Here, we can see the difference: either function allows 5 to be inserted at any of its identical values in the array. One returns the leftmost index, the other returns the rightmost.
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
This function goes beyond searching—it directly inserts the value into the array, maintaining the order. (Of course, there are also insort_right() and insort() functions available.)
# coding: utf-8
import bisect
def main() -> None:
# Init
arr = [1, 2, 5, 6, 8]
# Insert
bisect.insort_left(arr, 9)
bisect.insort_left(arr, 4)
bisect.insort_left(arr, 7)
bisect.insort_left(arr, 3)
# Show
print(f"arr: {arr}")
if __name__ == "__main__":
main()
Output:
arr: [1, 2, 3, 4, 5, 6, 7, 8, 9]
As you can see, new values are inserted without disrupting the sorted order of the array.