Python bisect & Sorted Lists — Core Concepts

The problem bisect solves

You have a sorted list and you want to either find an element or insert a new one while keeping the list sorted. You could call list.sort() after every insertion, but that costs O(n log n) each time. The bisect module finds the correct insertion point in O(log n) and inserts in O(n) — dominated by the list shift, not the search.

The four key functions

Function	Returns	Behavior with duplicates
bisect_left(a, x)	Index where x would go	Left of existing equal values
bisect_right(a, x)	Index where x would go	Right of existing equal values
insort_left(a, x)	None (modifies list)	Inserts left of equals
insort_right(a, x)	None (modifies list)	Inserts right of equals

bisect.bisect is an alias for bisect_right.

Left vs right: when it matters

import bisect

scores = [70, 80, 80, 90]
bisect.bisect_left(scores, 80)   # → 1 (before the first 80)
bisect.bisect_right(scores, 80)  # → 3 (after the last 80)

Use bisect_left when you want to find an existing element’s position. Use bisect_right when you want to insert after all equal elements (FIFO order for ties).

Pattern: grade lookup table

A classic use case is mapping numeric scores to letter grades:

import bisect

def grade(score, breakpoints=[60, 70, 80, 90], grades="FDCBA"):
    i = bisect.bisect(breakpoints, score)
    return grades[i]

print(grade(85))  # → 'B'
print(grade(92))  # → 'A'
print(grade(55))  # → 'F'

No chain of if/elif needed. The breakpoints list acts as a lookup table.

Pattern: maintaining a sorted collection

import bisect

leaderboard = []
for name, score in [("Alice", 300), ("Bob", 150), ("Carol", 450)]:
    bisect.insort(leaderboard, (score, name))

# leaderboard: [(150, 'Bob'), (300, 'Alice'), (450, 'Carol')]

Each insertion keeps the list sorted. Retrieving the top k players is a simple slice from the end.

The key parameter (Python 3.10+)

Since Python 3.10, bisect functions accept a key argument, similar to sorted():

import bisect
from dataclasses import dataclass

@dataclass
class Event:
    time: float
    name: str

events = [Event(1.0, "start"), Event(3.0, "middle"), Event(5.0, "end")]
pos = bisect.bisect_left(events, 2.5, key=lambda e: e.time)
# pos → 1, between "start" and "middle"

Before 3.10, you’d need a separate list of keys or a wrapper class.

Common misconception

People assume bisect searches and confirms the element exists. It doesn’t. bisect_left returns where the element would go. To check for existence, you must verify the element at that index:

def contains(sorted_list, target):
    i = bisect.bisect_left(sorted_list, target)
    return i < len(sorted_list) and sorted_list[i] == target

When NOT to use bisect

• If you’re inserting heavily and rarely searching, the O(n) list insertion dominates. Consider sortedcontainers.SortedList for O(log n) insert.
• If the data isn’t sorted, bisect gives wrong results silently. There’s no validation.
• For single lookups in unsorted data, a set or dict with O(1) average lookup is better.

The one thing to remember: bisect gives you O(log n) search in sorted lists and elegant lookup tables — but the list must actually be sorted, and bisect won’t tell you if it’s not.