Skip to content

[Python] Array Bisection Algorithm bisect Note

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:

  • a is a sorted array
  • x is the value to insert
  • lo is the starting point for evaluation, with a default of 0
  • hi is the endpoint for evaluation, defaulting to the length of the array
  • key is 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.

References

Read More

Tags:

Leave a Reply