The bisect module in Python

The bisect module in Python provides support for maintaining a list in sorted order without having to sort the list after each insertion. This module implements an algorithm known as binary search, which efficiently finds the position where an element should be inserted to keep the list sorted. This guide will cover the basics and advanced usage of the bisect module.

Overview of the bisect Module

The bisect module contains functions that work with sorted lists:

• bisect.bisect_left(a, x, lo=0, hi=len(a)): Locate the insertion point for x in a sorted list a to maintain sorted order. The return value is the index where x would go. If x is already present in a, the insertion point will be before (to the left of) any existing entries.
• bisect.bisect_right(a, x, lo=0, hi=len(a)) or bisect.bisect(a, x, lo=0, hi=len(a)): Similar to bisect_left(), but if x is already present, the insertion point will be after (to the right of) any existing entries.
• bisect.insort_left(a, x, lo=0, hi=len(a)): Insert x in a sorted list a at the position returned by bisect_left().
• bisect.insort_right(a, x, lo=0, hi=len(a)) or bisect.insort(a, x, lo=0, hi=len(a)): Insert x in a sorted list a at the position returned by bisect_right().

Importing the Module

Before using the bisect module, you need to import it:

import bisect

Using bisect_left

The bisect_left function finds the position where an element should be inserted to maintain order. If the element is already present, it returns the position before the first occurrence.

Example

import bisect

a = [1, 3, 3, 5, 7]
x = 3

# Find the insertion point for x
index = bisect.bisect_left(a, x)
print(index)  # Output: 1

Using bisect_right

The bisect_right function also finds the insertion point, but returns the position after the last occurrence of the element if it is already present.

Example

import bisect

a = [1, 3, 3, 5, 7]
x = 3

# Find the insertion point for x
index = bisect.bisect_right(a, x)
print(index)  # Output: 3

Using insort_left

The insort_left function inserts an element in the sorted list at the position determined by bisect_left.

Example

import bisect

a = [1, 3, 3, 5, 7]
x = 3

# Insert x into a at the position determined by bisect_left
bisect.insort_left(a, x)
print(a)  # Output: [1, 3, 3, 3, 5, 7]

Using insort_right

The insort_right function inserts an element in the sorted list at the position determined by bisect_right.

Example

import bisect

a = [1, 3, 3, 5, 7]
x = 3

# Insert x into a at the position determined by bisect_right
bisect.insort_right(a, x)
print(a)  # Output: [1, 3, 3, 3, 5, 7]

Advanced Usage

Custom Key Functions

You can use custom key functions with bisect operations, similar to the sorted function or list.sort method.

Example

Suppose you have a list of tuples and you want to maintain order based on the second element:

import bisect

data = [(1, 'apple'), (2, 'banana'), (2, 'cherry')]
key = lambda x: x[1]

# Find the insertion point for ('2', 'blueberry') based on the second element
index = bisect.bisect_left(data, (2, 'blueberry'), key=key)
print(index)  # Output: 2

# Insert ('2', 'blueberry') into the list
bisect.insort_left(data, (2, 'blueberry'), key=key)
print(data)  # Output: [(1, 'apple'), (2, 'banana'), (2, 'blueberry'), (2, 'cherry')]

Practical Examples

Example 1: Maintaining a Leaderboard

Consider maintaining a sorted leaderboard where players are inserted based on their scores.

import bisect

# List of player scores (sorted in descending order)
leaderboard = [100, 90, 80, 70, 60]

# New player score
new_score = 85

# Find the insertion point to keep the leaderboard sorted in descending order
index = bisect.bisect_left(leaderboard, new_score, key=lambda x: -x)
bisect.insort_left(leaderboard, new_score, key=lambda x: -x)

print(leaderboard)  # Output: [100, 90, 85, 80, 70, 60]

Example 2: Managing Event Timelines

You might need to insert events in a timeline where each event has a timestamp.

import bisect
from datetime import datetime

# List of events (each event is a tuple with a timestamp and description)
events = [
    (datetime(2023, 5, 31, 12, 0), 'Lunch'),
    (datetime(2023, 5, 31, 9, 0), 'Breakfast'),
    (datetime(2023, 5, 31, 18, 0), 'Dinner')
]

# Sort the initial list of events
events.sort()

# New event
new_event = (datetime(2023, 5, 31, 15, 0), 'Meeting')

# Find the insertion point for the new event
index = bisect.bisect_left(events, new_event)
bisect.insort_left(events, new_event)

for event in events:
    print(event)

# Output:
# (datetime.datetime(2023, 5, 31, 9, 0), 'Breakfast')
# (datetime.datetime(2023, 5, 31, 12, 0), 'Lunch')
# (datetime.datetime(2023, 5, 31, 15, 0), 'Meeting')
# (datetime.datetime(2023, 5, 31, 18, 0), 'Dinner')

The bisect module in Python is an invaluable tool for maintaining sorted lists efficiently. By leveraging the power of binary search, you can quickly find insertion points and keep your data ordered without the need for frequent sorting operations.