bisect Module: Binary Search in Sorted Lists

1Concept

The `bisect` module implements binary search algorithms for sorted sequences: `bisect_left` finds the insertion index for an element, and `insort` inserts an element in-place while preserving sorted order in O(log N) lookup time.

2Architecture Diagram

Sorted: [ 10, 20, 30, 40 ] ---> insort(25) ---> [ 10, 20, 25, 30, 40 ] in O(log N)

3Code Example

import bisect

grades = [60, 70, 80, 90]
letters = ['F', 'D', 'C', 'B', 'A']

def grade_score(score: int) -> str:
    idx = bisect.bisect_right(grades, score)
    return letters[idx]

print(f"Score 85 Grade: {grade_score(85)}")
print(f"Score 92 Grade: {grade_score(92)}")

# Maintaining sorted list
sorted_ids = [101, 105, 110]
bisect.insort(sorted_ids, 108)
print(f"Maintained sorted list: {sorted_ids}")

4Expected Output

Score 85 Grade: B
Score 92 Grade: A
Maintained sorted list: [101, 105, 108, 110]

5Key Takeaways

• ✓`bisect` requires the list to be strictly pre-sorted.
• ✓Ideal for breakpoint tables and interval search lookups.
• ✓Insertion with `insort` is O(log N) search + O(N) list shift; use `blist` or trees for large collections.