Python's bisect Module: Fast Binary Search on Sorted Lists

Why binary search needs a sorted list

Checking whether a value exists in an unsorted list means looking at every element in the worst case — O(n). If the list is sorted, you can do better: compare against the middle element, and depending on whether the target is smaller or larger, discard half the remaining list on every step. That's binary search, and it runs in O(log n) comparisons. The bisect module implements this directly on Python lists, but it trusts you that the list is sorted — running it on unsorted data doesn't raise an error, it just returns a meaningless position.

bisect_left vs bisect_right

Both functions return the index where a value could be inserted to keep the list sorted. They only differ when the value already appears in the list:

import bisect

data = [1, 3, 3, 3, 5, 7]

bisect.bisect_left(data, 3)    # 1 -- before the existing 3s
bisect.bisect_right(data, 3)   # 4 -- after the existing 3s
bisect.bisect_left(data, 4)    # 4 -- same for a value not present

bisect_left returns the position of the first existing occurrence, and bisect_right returns the position just past the last one. This matters if you're using the result to decide "does this value already exist": bisect_left(data, x) < len(data) and data[bisect_left(data, x)] == x tells you definitively, while just checking whether the returned index changed does not.

Keeping a list sorted with insort

Rather than finding a position and then inserting manually, insort_left and insort_right do both in one call:

scores = [55, 60, 72, 88]
bisect.insort(scores, 65)
print(scores)   # [55, 60, 65, 72, 88] -- still sorted

bisect.insort is an alias for insort_right. This is convenient for maintaining a small sorted list as values arrive one at a time — a leaderboard, a running list of timestamps, or a sorted set of thresholds — without calling list.sort() again after every insert, which would cost O(n log n) each time instead of the O(n) that a single insertion actually requires.

A practical example: grade boundaries

A classic use of bisect is mapping a numeric score onto a category using pre-sorted boundaries, without a chain of if/elif statements:

def grade(score, boundaries=(60, 70, 80, 90), letters="FDCBA"):
    index = bisect.bisect(boundaries, score)
    return letters[index]

print(grade(55))   # 'F'
print(grade(72))   # 'C'
print(grade(95))   # 'A'

Each boundary in (60, 70, 80, 90) is the cutoff below which the previous letter applies; bisect finds which "bucket" the score falls into in one call, and the code reads as a direct statement of the mapping rather than a sequence of comparisons that has to be read start to finish to understand. This pattern generalises to anything with ordered tiers — shipping cost by weight, tax brackets, log severity thresholds.

Complexity and caveats

It's worth being precise about what bisect actually speeds up. Finding the position is O(log n) thanks to binary search. But list.insert() at an arbitrary position is still O(n), because every element after that position has to shift over in memory — bisect does not change this. For a workload dominated by lookups on a mostly-static sorted list, this is a clear win over a linear scan. For a workload with heavy interleaved insertion and lookup on a large list, a different structure such as a balanced tree or the heapq module's heap, depending on what operations you actually need, may scale better than repeated list insertion. See the bisect module documentation for the exact signatures of the lo/hi/key parameters that let you search a sub-range or bisect by a derived value instead of the raw element.