Python bisect: Tutorial to the Array Bisection Algorithm

Introduction

The bisect module in Python provides tools for maintaining a sorted list without needing to reorder it after each insertion. This is especially useful when handling long lists with expensive comparison operations, improving efficiency compared to linear searches or frequent reordering.

Main Functions of the bisect Module

The bisect module provides several key functions:

• bisect_left(a, x, lo=0, hi=len(a), *, key=None): Returns the insertion point for x in list a to maintain sorted order. If x is already present, the insertion point will be before existing occurrences.
• bisect_right(a, x, lo=0, hi=len(a), *, key=None): Similar to bisect_left(), but returns an insertion point after existing occurrences of x in a.
• insort_left(a, x, lo=0, hi=len(a), *, key=None): Inserts x into list a in sorted order, before existing occurrences of x.
• insort_right(a, x, lo=0, hi=len(a), *, key=None): Similar to insort_left(), but inserts x after existing occurrences.

Practical Examples with bisect Module

Inserting into a Sorted List

Let’s say we have a sorted list and want to insert a new element while maintaining order:

import bisect

# Sorted list
lst = [10, 20, 30, 40, 50]

# New element to insert
new_element = 35

# Find the insertion position
position = bisect.bisect_left(lst, new_element)

# Insert the element at the found position
bisect.insort_left(lst, new_element)

print(lst)

Output:

[10, 20, 30, 35, 40, 50]

Binary Search in a Sorted List with bisect Module

The bisect module can be used to implement an efficient binary search:

import bisect

def binary_search(lst, element):
    position = bisect.bisect_left(lst, element)
    if position != len(lst) and lst[position] == element:
        return position
    else:
        return -1

# Sorted list
lst = [5, 10, 15, 20, 25]

# Element to search
element = 15

# Execute binary search
result = binary_search(lst, element)

print(f'Element found at position: {result}')

Output:

Element found at position: 2

Assigning Values Based on Intervals

You can use bisect to map values to specific intervals:

import bisect

def assign_grade(score, intervals=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect.bisect(intervals, score)
    return grades[i]

# List of scores
scores = [55, 65, 75, 85, 95]

# Assign grades to scores
grades = [assign_grade(s) for s in scores]

print(grades)

Output:

['F', 'D', 'C', 'B', 'A']

Using Custom Objects

The bisect module can be used with custom objects by defining the __lt__ method:

import bisect

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __lt__(self, other):
        return self.age < other.age

    def __repr__(self):
        return f'{self.name} ({self.age})'

# List of people sorted by age
people = [
    Person('Alice', 30),
    Person('Bob', 25),
    Person('Charlie', 35)
]

# Sort the list
people.sort()

# New person to insert
new_person = Person('David', 28)

# Insert the new person while maintaining order
bisect.insort_left(people, new_person)

print(people)

Output:

[Bob (25), David (28), Alice (30), Charlie (35)]

Performance Considerations

The search functions in the bisect module operate in O(log n) time, making them efficient for finding insertion points in sorted lists. However, the insertion functions (insort_left and insort_right) have O(n) complexity due to the cost of shifting elements during insertion.

References

For further reading on the bisect module and its applications, check out the following resources:

• Official Python documentation on the bisect module

Conclusion

The bisect module is a powerful tool for handling sorted lists in Python, providing efficient functions for insertion and search. Understanding and utilizing it can significantly improve the performance of applications that require frequent operations on ordered data.