Using Bisect Module

Python
from bisect import bisect_left, bisect_right, insort_left, insort_right

sorted_list = [1, 3, 4, 4, 6, 8]

# Find insertion point (no mutation)
idx = bisect_right(sorted_list, 4)  # 4 -> insert after existing 4s

# Insert while keeping list sorted
insort_right(sorted_list, 5)  # sorted_list -> [1, 3, 4, 4, 5, 6, 8]

1. Decide left vs right semantics for duplicate handling:
   • bisect_left / insort_left: insertion point before existing equal entries
   • bisect_right / insort_right (aka bisect/insort): insertion point after existing equal entries
2. Use bisect_* when you only need the index (e.g., for grading/lookup tables, avoiding a full insert).
3. Use insort_* when you need to mutate the list to keep it sorted after adding a value.
4. For custom sort keys (Python 3.10+), pass key= instead of pre-transforming the list:

   Python
   bisect_left(data, target, key=lambda x: x.value)

5. For narrowing search range, use lo and hi parameters to limit the search to a slice [lo, hi).
6. Never call these on an unsorted list — behavior is undefined/incorrect.

Example 1: Grade lookup table Input:

Python
def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    from bisect import bisect
    i = bisect(breakpoints, score)
    return grades[i]

[grade(s) for s in [55, 60, 61, 89, 90, 100]]

Output: ['F', 'D', 'D', 'C', 'A', 'A']

Example 2: Insert maintaining order with objects Input:

Python
from bisect import insort_right
from dataclasses import dataclass

@dataclass
class Event:
    time: int

events = [Event(1), Event(5), Event(10)]
insort_right(events, Event(7), key=lambda e: e.time)
[e.time for e in events]

Output: [1, 5, 7, 10]

Example 3: Finding index without inserting Input:

Python
from bisect import bisect_left
data = [10, 20, 30, 40]
bisect_left(data, 25)

Output: 2