Bisect Module Complexity¶

The bisect module provides binary search operations for sorted lists.

Operations¶

Operation	Time	Space	Notes
`bisect_left(a, x)`	O(log n)	O(1)	Find leftmost position
`bisect_right(a, x)`	O(log n)	O(1)	Find rightmost position
`bisect(a, x)`	O(log n)	O(1)	Alias for bisect_right
`insort_left(a, x)`	O(n)	O(1)	O(log n) search + O(n) insert (shifts elements in place)
`insort_right(a, x)`	O(n)	O(1)	O(log n) search + O(n) insert (shifts elements in place)
`insort(a, x)`	O(n)	O(1)	Alias for insort_right

Space Complexity¶

Binary search operations: O(1) additional space
Insert operations: O(1) additional space (shifts elements within the existing list)

Implementation Details¶

Binary Search Guarantee¶

import bisect

# Must be sorted!
sorted_list = [1, 3, 3, 3, 5, 7, 9]

# bisect_left: leftmost insertion point
pos = bisect.bisect_left(sorted_list, 3)  # O(log n), pos = 1
# Insert here to keep list sorted (before all 3's)

# bisect_right: rightmost insertion point
pos = bisect.bisect_right(sorted_list, 3)  # O(log n), pos = 4
# Insert here to keep list sorted (after all 3's)
# Both halve the search range each step, so a run of equal values costs no
# more than a unique one

Finding Elements¶

import bisect

sorted_list = [1, 3, 5, 7, 9]

# Check if element exists
def exists(sorted_list, x):
    pos = bisect.bisect_left(sorted_list, x)
    return pos < len(sorted_list) and sorted_list[pos] == x

exists(sorted_list, 5)  # True - O(log n)
exists(sorted_list, 4)  # False - O(log n)

Common Use Cases¶

Sorted Insert¶

import bisect

sorted_list = [1, 3, 5, 7]

# Insert while maintaining order - O(n) overall
# (O(log n) search + O(n) shift)
bisect.insort(sorted_list, 4)  # [1, 3, 4, 5, 7]

# Better for many insertions: use list, then sort
# Multiple inserts: O(n log n) with sort
# vs O(n²) with repeated insort

Finding Ranges¶

import bisect

# Find all equal elements
sorted_list = [1, 3, 3, 3, 5, 7, 9]
target = 3

left = bisect.bisect_left(sorted_list, target)
right = bisect.bisect_right(sorted_list, target)

equals = sorted_list[left:right]  # All 3's - O(log n) search

Finding Insertion Point for Range¶

import bisect

# Find where range [a, b] fits in sorted list
sorted_list = [1, 5, 10, 15, 20]
target_range = (7, 12)

# Position to insert start of range
start_pos = bisect.bisect_right(sorted_list, target_range[0])  # O(log n)

# Position to insert end of range
end_pos = bisect.bisect_left(sorted_list, target_range[1])  # O(log n)
# Two independent searches: O(log n) total, not O(n)

print(f"Insert range {target_range} at positions {start_pos}-{end_pos}")

Performance Comparison¶

Searching in Sorted Data¶

import bisect

data = sorted(range(1000000))

# Bad: Linear search - O(n)
found = 500000 in data  # Scans linearly

# Good: Binary search - O(log n)
pos = bisect.bisect_left(data, 500000)  # Much faster!
found = pos < len(data) and data[pos] == 500000

Maintaining Sorted Lists¶

import bisect

# Many insertions scenario
sorted_list = [1, 3, 5, 7, 9]

# Bad: Multiple insort - O(n²)
for item in [2, 4, 6, 8]:
    bisect.insort(sorted_list, item)  # O(n) each

# Better: Collect, sort once - O(n log n)
sorted_list.extend([2, 4, 6, 8])
sorted_list.sort()  # Single O(n log n) operation

Detailed Examples¶

Grade Ranges¶

import bisect

# Map scores to grades
grade_breaks = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']

def get_grade(score):
    i = bisect.bisect(grade_breaks, score)
    return grades[i]

print(get_grade(85))  # 'B' - O(log n)
print(get_grade(95))  # 'A' - O(log n)

Timestamp Lookup¶

import bisect
from datetime import datetime, timedelta

# Find events in a time range
events = [
    (datetime(2024, 1, 1, 10), 'event1'),
    (datetime(2024, 1, 1, 12), 'event2'),
    (datetime(2024, 1, 1, 15), 'event3'),
    (datetime(2024, 1, 1, 18), 'event4'),
]

timestamps = [e[0] for e in events]

# Find events after specific time
target = datetime(2024, 1, 1, 14)
idx = bisect.bisect_right(timestamps, target)
later_events = events[idx:]  # O(log n) search

print(later_events)  # Events at 3pm and 6pm

Advanced: Custom Key Functions¶

import bisect
from bisect import bisect_right

# Custom objects - compare by second element
data = [('a', 1), ('b', 3), ('c', 5)]
keys = [x[1] for x in data]  # O(n) - building the key list dominates

# Find position for ('d', 4)
pos = bisect_right(keys, 4)  # O(log n)
data.insert(pos, ('d', 4))  # O(n) - shifts the tail
# Rebuilding keys per search makes the whole thing O(n); keep it alongside
# data instead

Since Python 3.10 every function in the module takes a key argument, which removes the parallel list:

import bisect

data = [('a', 1), ('b', 3), ('c', 5)]

# key runs once per probe, so no parallel list is needed
pos = bisect.bisect_right(data, 4, key=lambda item: item[1])  # O(log n) key calls
data.insert(pos, ('d', 4))  # O(n) - shifts the tail

Which to prefer depends on how many searches share the keys: a parallel list costs O(n) once and no calls per search, while key costs nothing up front and one call per probe.

Important Notes¶

Sorted Data Requirement

The input list MUST be sorted for binary search to work correctly.

import bisect

# Wrong: Data not sorted
unsorted = [3, 1, 4, 1, 5]
pos = bisect.bisect(unsorted, 2)  # Incorrect result!

Amortized Efficiency

For many insertions:

Multiple insort() calls: O(n²) overall
Collect then single sort(): O(n log n) overall

Choose based on your access patterns.

Version Notes¶

Python 3.10+: key parameter added to every function in the module