bisect

The bisect module uses binary search to find where an item belongs in an already-sorted sequence, letting you locate or insert values in O(log n) instead of scanning linearly.

Once a sequence is sorted, you don't need to scan it item by item to find where a value belongs -- binary search narrows the range in half at each step. The bisect module provides that binary search directly for sorted lists, both to find an insertion point and to insert while keeping the list sorted.

What the bisect Module Does

bisect works only on sequences that are already sorted in ascending order -- it does not sort for you, and its behavior is undefined (it will not raise an error, but will return meaningless results) if the input isn't sorted. Given that precondition, it finds insertion points and performs insertions in O(log n) comparisons, versus O(n) for a linear scan.

import bisect

scores = [10, 20, 30, 40, 50]
index = bisect.bisect_left(scores, 25)
print(index)   # 2 -- 25 would be inserted at index 2 to keep the list sorted

bisect_left vs bisect_right

Both functions return an insertion index that keeps the sequence sorted; they differ only in how they handle a value that already equals an existing element. bisect_left returns the leftmost (first) valid position -- inserting there would place the new value before any equal existing elements. bisect_right (an alias, bisect, points to the same function) returns the rightmost valid position -- after any equal elements. bisect() alone is shorthand for bisect_right().

The distinction matters when duplicates exist and you need to insert consistently before or after them -- e.g. maintaining stable order for equal-priority items.

nums = [1, 3, 3, 3, 5]
print(bisect.bisect_left(nums, 3))   # 1 -- before the existing 3s
print(bisect.bisect_right(nums, 3))  # 4 -- after the existing 3s
print(bisect.bisect(nums, 3))         # 4 -- same as bisect_right

insort_left and insort_right: Insert While Staying Sorted

insort_left(seq, item) and insort_right(seq, item) (insort() is shorthand for insort_right) combine the bisect step with list.insert(), inserting item at the correct position in one call so the sequence remains sorted. Each call is still O(n) overall because list.insert() itself must shift elements, even though finding the position is O(log n).

insort avoids the two-step 'find index, then insert' pattern, but it's still fundamentally a list, so repeated insertions are O(n) each due to the underlying shift -- for very frequent insertions, consider heapq or a different structure.

import bisect

sorted_list = [10, 20, 40, 50]
bisect.insort(sorted_list, 30)
print(sorted_list)   # [10, 20, 30, 40, 50] -- stays sorted, one call

Practical Use: Grade Lookup Tables

A classic bisect use case is mapping a numeric score into a category using parallel 'breakpoints' and 'grades' lists -- bisect finds which bucket a score falls into without an if/elif chain.

This avoids a manual if score >= 90: ... elif score >= 80: ... chain, and scales to any number of breakpoints without adding more branches.

import bisect

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

def grade(score: int) -> str:
    index = bisect.bisect(breakpoints, score)
    return grades[index]

print(grade(85))   # 'B'
print(grade(59))   # 'F'
print(grade(90))   # 'A' -- bisect_right means a score exactly at a breakpoint rounds up

Maintaining a Sorted List Efficiently

When you need to repeatedly check membership or find neighbors in a sorted collection that also changes over time, bisect keeps the list sorted incrementally instead of re-sorting from scratch after every insertion (sorted() after each insert would be O(n log n) per insert, versus O(n) for insort's shift, dominated by the O(log n) search).

import bisect

leaderboard: list[int] = []
for score in [88, 95, 72, 99, 60]:
    bisect.insort(leaderboard, score)
print(leaderboard)   # [60, 72, 88, 95, 99] -- always sorted after each insertion

Common Mistakes

The most common bisect mistake is calling it on an unsorted sequence -- there's no validation, so results are simply wrong (not an error) if the sequence isn't sorted. A second common mistake is treating bisect_left and bisect_right as interchangeable when duplicates are present.

Complete Example: Version Lookup

Tuples compare element by element, so bisect works directly on sorted tuples like version numbers without any custom key logic.

import bisect

released_versions = [(1, 0), (1, 5), (2, 0), (2, 3)]

def latest_supported(target: tuple[int, int]) -> tuple[int, int] | None:
    index = bisect.bisect_right(released_versions, target)
    return released_versions[index - 1] if index > 0 else None

print(latest_supported((1, 8)))   # (1, 5) -- latest release at or before 1.8
print(latest_supported((0, 9)))   # None -- nothing released yet

Key Takeaways

bisect requires its input to already be sorted -- it does not sort for you, and gives meaningless results on unsorted input without raising an error.

bisect_left and bisect_right differ only in where they place a value equal to existing elements (before vs after).

bisect() and insort() are shorthand for bisect_right() and insort_right().

insort inserts in the correct sorted position in one call, but the underlying list.insert() shift keeps each call O(n).

Binary search via bisect is O(log n) to find a position, which beats a linear scan for any reasonably sized sorted sequence.

unsorted = [5, 1, 9, 3] index = bisect.bisect(unsorted, 4) # meaningless result -- no error raised sorted_list = sorted(unsorted) index = bisect.bisect(sorted_list, 4) bisect assumes its input is already sorted and does not check; running it on unsorted data returns a syntactically valid but logically meaningless index.

bisect.insort still relies on list.insert(), which shifts elements and is O(n) per call -- fine for occasional insertions into a large list, but a poor fit for very high-frequency insertion.

What precondition does every bisect function assume about its input sequence, and what happens if that precondition is violated?

It assumes the sequence is already sorted in ascending order; if it isn't, bisect does not raise an error -- it silently returns an index that does not correctly reflect where the value belongs.

What is the difference between bisect_left(seq, x) and bisect_right(seq, x) when x already appears in seq?

bisect_left returns the index before any existing elements equal to x (the leftmost valid insertion point); bisect_right returns the index after them (the rightmost valid insertion point). They only differ when duplicates of x are present.

Why is bisect.insort still O(n) overall even though finding the insertion point is O(log n)?

Finding the position via binary search is O(log n), but actually inserting into a Python list requires shifting every subsequent element over by one, which is O(n) -- the search is fast, but the insertion itself is not.

How can bisect be used to implement a grade/category lookup without an if/elif chain?

Store the boundary values in a sorted 'breakpoints' list and the corresponding labels in a parallel list one longer; bisect(breakpoints, value) returns the index into the labels list, replacing a manual chain of comparisons with one binary search.

When would you prefer to keep a list sorted incrementally with bisect.insort rather than appending and re-sorting with sorted() after each insertion?

When insertions are interleaved with reads that need the list sorted at every point -- bisect.insort keeps it sorted after each single insertion at a cost dominated by an O(n) shift, while re-sorting from scratch after every insert would cost O(n log n) each time.

Write a function that checks whether a value exists in a sorted list using bisect (i.e. without a linear 'in' scan).

import bisect def contains(sorted_seq: list[int], value: int) -> bool: index = bisect.bisect_left(sorted_seq, value) return index < len(sorted_seq) and sorted_seq[index] == value print(contains([1, 3, 5, 7, 9], 5)) # True print(contains([1, 3, 5, 7, 9], 6)) # False bisect_left finds where value would go; if that index is in range and the element actually there equals value, it's present -- this is an O(log n) membership check versus O(n) for a linear scan.

What does this print?

1 4 -- bisect_left returns the index before the run of 2s (index 1), and bisect_right returns the index after the run (index 4); subtracting gives the count of 2s in the list (3).

Write a function that inserts a new score into a sorted leaderboard list, keeping it sorted, and returns the new score's rank (1-based, highest score = rank 1).

import bisect def insert_and_rank(leaderboard: list[int], score: int) -> int: bisect.insort(leaderboard, score) index_from_low = leaderboard.index(score) return len(leaderboard) - index_from_low board = [60, 75, 90] print(insert_and_rank(board, 80)) # inserts 80, returns its rank print(board) bisect.insort keeps the list sorted ascending in one call; since rank 1 means highest score, the rank is the count of items at or after this score's position, computed as len(leaderboard) minus its ascending index -- inserting 80 into [60, 75, 90] gives [60, 75, 80, 90] and rank 2.

import bisect
nums = [1, 2, 2, 2, 3]
print(bisect.bisect_left(nums, 2), bisect.bisect_right(nums, 2))