Python bisect Module

In this guide, you'll explore Python's bisect module, which manages sorted lists. Learn its key functions and examples for efficient list operations.

The bisect module in Python provides support for maintaining a list in sorted order without having to sort the list after each insertion. It is useful for handling sorted sequences and can be used to perform binary search operations to find insertion points.

Table of Contents

1. Introduction
2. Functions in bisect
   • bisect_left
   • bisect_right
   • insort_left
   • insort_right
3. Examples
   • Finding Insertion Points
   • Inserting Elements into a Sorted List
4. Real-World Use Case
5. Conclusion
6. References

Introduction

The bisect module provides a set of functions to manage sorted lists using the bisection algorithm. It helps to insert elements into a list while maintaining the order, as well as to find the position where an element should be inserted to keep the list sorted.

Functions in bisect

bisect_left

The bisect_left function returns the insertion point for an element in a sorted list to maintain sorted order. If the element is already present, the insertion point will be before the existing element.

import bisect

data = [1, 2, 4, 4, 5]
print(bisect.bisect_left(data, 4))

Output:

2

bisect_right

The bisect_right function returns the insertion point for an element in a sorted list to maintain sorted order. If the element is already present, the insertion point will be after the existing element.

import bisect

data = [1, 2, 4, 4, 5]
print(bisect.bisect_right(data, 4))

Output:

4

insort_left

The insort_left function inserts an element into the list while maintaining sorted order. If the element is already present, it will be inserted before the existing element.

import bisect

data = [1, 2, 4, 4, 5]
bisect.insort_left(data, 4)
print(data)

Output:

[1, 2, 4, 4, 4, 5]

insort_right

The insort_right function inserts an element into the list while maintaining sorted order. If the element is already present, it will be inserted after the existing element.

import bisect

data = [1, 2, 4, 4, 5]
bisect.insort_right(data, 4)
print(data)

Output:

[1, 2, 4, 4, 4, 5]

Examples

Finding Insertion Points

Determine where to insert an element to keep the list sorted.

import bisect

data = [1, 3, 4, 7]
print(bisect.bisect_left(data, 5))
print(bisect.bisect_right(data, 5))

Output:

3
3

Inserting Elements into a Sorted List

Insert elements into a sorted list while maintaining the order.

import bisect

data = [1, 3, 4, 7]
bisect.insort_left(data, 5)
print(data)

Output:

[1, 3, 4, 5, 7]

Real-World Use Case

Maintaining a Leaderboard

Suppose you are implementing a leaderboard for a game. You can use the bisect module to insert scores into a sorted list efficiently.

import bisect

scores = []
bisect.insort_left(scores, 100)
bisect.insort_left(scores, 200)
bisect.insort_left(scores, 150)
print(scores)

Output:

[100, 150, 200]

Conclusion

The bisect module in Python provides efficient algorithms for maintaining sorted lists and finding insertion points. By using the functions in this module, you can manage sorted sequences more effectively, which is useful in various applications like maintaining leaderboards, implementing search algorithms, and more.

References

• Python bisect module documentation