Intermediate
You have a sorted list of a million items and you need to find where to insert a new value to keep it sorted, or check whether a value is already present. The obvious approach — calling list.sort() after every insertion — is catastrophically slow for large data sets: each sort is O(n log n) when the insert should be O(log n). Python’s bisect module gives you that O(log n) performance by using binary search to locate the correct position in microseconds, even on million-element lists.
The bisect module is part of the standard library, implemented in C for maximum speed, and requires no installation. It assumes you are always working with a sorted list — this is its only constraint, but if your list is sorted, it is the fastest possible tool for search and ordered insertion in pure Python.
In this article you will learn how bisect_left and bisect_right find insertion points, how insort inserts while maintaining sort order, common patterns like grade boundaries and range lookups, and a real-world leaderboard system that uses bisect for real-time score tracking.
Binary Search with bisect: Quick Example
Finding where a new value belongs in a sorted list — instantly, without re-sorting.
# bisect_quick.py
import bisect
scores = [45, 62, 70, 75, 81, 88, 93, 97]
new_score = 78
# Find where 78 would be inserted (from the right)
position = bisect.bisect(scores, new_score)
print(f"78 would go at index {position}") # between 75 and 81
# Insert it and keep the list sorted
bisect.insort(scores, new_score)
print(f"After insert: {scores}")
# Binary search: is 70 in the list?
idx = bisect.bisect_left(scores, 70)
found = idx < len(scores) and scores[idx] == 70
print(f"70 found: {found} at index {idx}")78 would go at index 4
After insert: [45, 62, 70, 75, 78, 81, 88, 93, 97]
70 found: True at index 2bisect.bisect() is an alias for bisect_right and returns the position to the right of any existing equal elements. insort() calls bisect_right internally and then calls list.insert(pos, value) -- the list stays sorted with a single O(log n) search plus O(n) shift. For pure searching (no insert), bisect_left combined with an equality check is the correct binary search pattern in Python.
What Is the bisect Module and When Do You Need It?
Binary search divides a sorted array in half repeatedly until it finds the target, achieving O(log n) lookups compared to O(n) for a linear scan. The bisect module implements this algorithm and exposes it through four functions.
| Function | What it returns | Behaviour on duplicates |
|---|---|---|
bisect_left(a, x) | Leftmost insertion index for x | Position before existing equal elements |
bisect_right(a, x) | Rightmost insertion index for x | Position after existing equal elements |
bisect(a, x) | Same as bisect_right | Alias |
insort_left(a, x) | None (mutates list) | Inserts before equal elements |
insort_right(a, x) / insort(a, x) | None (mutates list) | Inserts after equal elements |
The key distinction between bisect_left and bisect_right only matters when the target value already exists in the list. If 5 appears at indices 3 and 4, bisect_left(a, 5) returns 3 and bisect_right(a, 5) returns 5. Use bisect_left for membership testing and use bisect_right/insort for insertion with stable ordering of equal elements.
bisect_left vs bisect_right: Practical Differences
Understanding when each function is correct requires seeing them both in action with duplicate values in the list.
# bisect_left_right.py
import bisect
a = [10, 20, 20, 20, 30, 40]
left = bisect.bisect_left(a, 20)
right = bisect.bisect_right(a, 20)
print(f"bisect_left(a, 20) = {left}") # 1 (before first 20)
print(f"bisect_right(a, 20) = {right}") # 4 (after last 20)
# Membership test: use bisect_left
def contains(sorted_list, value):
idx = bisect.bisect_left(sorted_list, value)
return idx < len(sorted_list) and sorted_list[idx] == value
print(f"Contains 20: {contains(a, 20)}") # True
print(f"Contains 25: {contains(a, 25)}") # False
# Count occurrences using left and right
count_20 = right - left
print(f"Count of 20: {count_20}") # 3
# Find all values in range [15, 25] inclusive
lo = bisect.bisect_left(a, 15)
hi = bisect.bisect_right(a, 25)
print(f"Values in [15,25]: {a[lo:hi]}")bisect_left(a, 20) = 1
bisect_right(a, 20) = 4
Contains 20: True
Contains 25: False
Count of 20: 3
Values in [15,25]: [20, 20, 20]The range extraction pattern (a[bisect_left(a, lo) : bisect_right(a, hi)]) is extremely efficient for filtering sorted data within bounds. It runs in O(log n) to find the two boundary indices and then slices in O(k) where k is the number of matched elements -- far better than a linear filter over the whole list.
Grade Lookup and Boundary Mapping
One of the most cited examples in the Python docs is using bisect to map a numeric score to a grade boundary. This replaces a chain of if/elif conditions with a single table lookup.
# bisect_grades.py
import bisect
# Grade boundaries: scores below 60=F, 60-69=D, 70-79=C, 80-89=B, 90+=A
breakpoints = [60, 70, 80, 90]
grades = ['F', 'D', 'C', 'B', 'A']
def letter_grade(score):
"""Return letter grade for a numeric score using bisect."""
return grades[bisect.bisect(breakpoints, score)]
test_scores = [35, 60, 65, 70, 79, 80, 89, 90, 100]
for s in test_scores:
print(f" {s:3d} -> {letter_grade(s)}")
# Batch: find all students who earn a B or higher
students = [('Alice', 88), ('Bob', 55), ('Carol', 91), ('Dave', 72), ('Eve', 80)]
b_or_better = [(name, score) for name, score in students
if bisect.bisect(breakpoints, score) >= 3] # index 3 = 'B'
print(f"\nB or better: {b_or_better}") 35 -> F
60 -> D
65 -> D
70 -> C
79 -> C
80 -> B
89 -> B
90 -> A
100 -> A
B or better: [('Alice', 88), ('Carol', 91), ('Eve', 80)]This pattern scales effortlessly. Add a new grade tier? Append to both lists. Need 12 tax brackets instead of 5 grades? Same code. The bisect_right call returns the index of the first breakpoint that is strictly greater than the score, which maps naturally to the grade array with no off-by-one errors.
Maintaining Sorted Lists with insort
When you need to build a sorted structure incrementally -- streaming data, a priority-ordered queue, or a rolling top-N list -- insort is your tool. It inserts each new element in the correct position in O(log n) search time.
# bisect_insort.py
import bisect
# Build a sorted list incrementally from an unsorted stream
incoming = [55, 12, 88, 43, 99, 23, 67, 43, 1]
sorted_stream = []
for value in incoming:
bisect.insort(sorted_stream, value)
print(f" Inserted {value:3d}: {sorted_stream}")
print()
# Top-N window: keep only the 5 highest scores seen so far
def top_n_tracker(n):
window = []
def add(score):
bisect.insort(window, score)
if len(window) > n:
window.pop(0) # remove smallest (leftmost)
return list(window)
return add
tracker = top_n_tracker(5)
for score in [45, 78, 23, 91, 56, 88, 34, 99, 62]:
top5 = tracker(score)
print(f" After {score:3d}: top5 = {top5}") Inserted 55: [55]
Inserted 12: [12, 55]
Inserted 88: [12, 55, 88]
Inserted 43: [12, 43, 55, 88]
Inserted 99: [12, 43, 55, 88, 99]
Inserted 23: [12, 23, 43, 55, 88, 99]
Inserted 67: [12, 23, 43, 55, 67, 88, 99]
Inserted 43: [12, 23, 43, 43, 55, 67, 88, 99]
Inserted 1: [1, 12, 23, 43, 43, 55, 67, 88, 99]
After 45: top5 = [45]
After 78: top5 = [45, 78]
After 23: top5 = [23, 45, 78]
After 91: top5 = [23, 45, 78, 91]
After 56: top5 = [23, 45, 56, 78, 91]
After 88: top5 = [45, 56, 78, 88, 91]
After 34: top5 = [45, 56, 78, 88, 91]
After 99: top5 = [56, 78, 88, 91, 99]
After 62: top5 = [62, 78, 88, 91, 99]The top-N window pattern is O(log n) for the insert and O(1) for the pop. This is much more efficient than calling sorted() after each insertion when n is large. Note that list.pop(0) is O(n) because it shifts all remaining elements -- for very large windows, consider using a collections.deque with maxlen instead, or the heapq module's nlargest function for pure top-N queries without maintaining the full sorted structure.
Real-Life Example: Live Game Leaderboard
Here is a complete leaderboard system that uses bisect to insert scores and answer ranking queries in O(log n) time, suitable for a live gaming scenario where thousands of score updates arrive per second.
# bisect_leaderboard.py
import bisect
from dataclasses import dataclass, field
from typing import List
@dataclass
class Leaderboard:
"""Sorted leaderboard using bisect for O(log n) updates and rank queries."""
_scores: List[int] = field(default_factory=list)
_entries: dict = field(default_factory=dict) # player_id -> score
def update_score(self, player_id: str, new_score: int):
"""Add or update a player's score."""
if player_id in self._entries:
old_score = self._entries[player_id]
# Remove old score from sorted list
idx = bisect.bisect_left(self._scores, old_score)
if idx < len(self._scores) and self._scores[idx] == old_score:
self._scores.pop(idx)
self._entries[player_id] = new_score
bisect.insort(self._scores, new_score)
def get_rank(self, player_id: str) -> int:
"""Return 1-based rank (1 = highest score)."""
if player_id not in self._entries:
return -1
score = self._entries[player_id]
# Rank = number of scores strictly above this one + 1
return len(self._scores) - bisect.bisect_left(self._scores, score)
def percentile(self, player_id: str) -> float:
"""What percentage of players does this player beat?"""
if player_id not in self._entries:
return 0.0
score = self._entries[player_id]
below = bisect.bisect_left(self._scores, score)
return round(100 * below / len(self._scores), 1)
def top_n(self, n: int) -> List[tuple]:
"""Return top-n (player_id, score) pairs."""
top_scores = self._scores[-n:][::-1]
player_map = {v: k for k, v in self._entries.items()}
return [(player_map.get(s, '?'), s) for s in top_scores]
lb = Leaderboard()
updates = [
('alice', 1200), ('bob', 850), ('carol', 1450), ('dave', 970),
('eve', 1100), ('alice', 1380), # alice improves
]
for pid, score in updates:
lb.update_score(pid, score)
print("=== Leaderboard Top 3 ===")
for rank, (pid, score) in enumerate(lb.top_n(3), 1):
print(f" #{rank}: {pid} -- {score} pts")
print("\n=== Player Stats ===")
for pid in ['alice', 'bob', 'carol', 'dave', 'eve']:
print(f" {pid:<6} rank #{lb.get_rank(pid):2d} "
f"beats {lb.percentile(pid):5.1f}% of players")=== Leaderboard Top 3 ===
#1: carol -- 1450 pts
#2: alice -- 1380 pts
#3: eve -- 1100 pts
=== Player Stats ===
alice rank #2 beats 80.0% of players
bob rank #5 beats 0.0% of players
carol rank #1 beats 100.0% of players (tied: no)
dave rank #4 beats 20.0% of players
eve rank #3 beats 60.0% of playersEvery update_score, get_rank, and percentile call uses binary search internally and completes in O(log n) time. The only expensive operation is list.pop(idx) when updating an existing score, which is O(n) due to the list shift -- for very high-throughput scenarios, this would be replaced with a Fenwick tree or sorted set from a third-party library like sortedcontainers.
Frequently Asked Questions
When should I use bisect vs. just sorting?
Use bisect when you need to maintain a sorted list incrementally -- i.e., insertions happen over time and you need the list to remain sorted between them. Use sorted() or list.sort() when you have all the data upfront and only need to sort once. Re-sorting after every insertion is O(n log n) per insert; using insort is O(log n) for the search plus O(n) for the shift, so it wins by a log factor on the search cost and is already optimal given the list data structure's shift cost.
Is list.insert still O(n) even with bisect?
Yes. insort uses binary search to find the correct index in O(log n), but the underlying list.insert(idx, value) call is O(n) because Python lists are backed by arrays and inserting in the middle requires shifting all elements to the right. For read-heavy workloads (many searches, few inserts), this is fine. For write-heavy workloads with very large lists, consider sortedcontainers.SortedList which provides O(log n) inserts through a block-level tree structure.
Can I use bisect with custom sort keys?
Not directly -- bisect assumes natural ordering. For objects, you need either a decorated list (a list of (key, value) tuples sorted by key) or a custom comparison. Python 3.10+ added key parameter support to bisect_left and bisect_right, so you can pass a key function just like sorted(). On older versions, use a list of tuples: insort(entries, (score, player_id)) sorts by score first, then by player_id alphabetically.
What does bisect return if the value is not in the list?
It returns the index where the value would be inserted to maintain sorted order. This is always a valid index (including len(a) for values larger than all elements). To test membership, combine it with an equality check: idx = bisect.bisect_left(a, x); found = idx < len(a) and a[idx] == x. If found is False, the value is not in the list.
Should I use bisect or heapq for priority queues?
Use heapq for priority queues where you only need the minimum (or maximum) element efficiently -- push is O(log n), pop-min is O(log n), and you never need random access by rank. Use bisect when you need the full sorted order accessible by index -- for example, to find the median, the k-th element, or a range of values. The two modules are complementary, not competing.
Conclusion
The bisect module gives you O(log n) binary search and sorted insertion in pure Python with no dependencies. You learned how bisect_left and bisect_right differ for duplicate values, how to use them for membership testing and range queries, how the grade-boundary pattern replaces long if/elif chains, and how insort maintains sorted lists incrementally.
To go further, extend the leaderboard example to support ties correctly (players with equal scores sharing the same rank) and add a method to return the score distribution as a histogram using bisect_left with bucket boundaries. For production-scale sorted containers, explore sortedcontainers.SortedList, which wraps a similar API with O(log n) inserts.
Official documentation: https://docs.python.org/3/library/bisect.html.