Efficient Searching with Python `bisect`

The bisect module in the Python standard library performs binary search on sorted lists. It finds the position where a value should be inserted to maintain sorted order, and it can insert values directly. The search is O(log n), far faster than scanning a list linearly when the list is large.

python

import bisect
 
scores = [60, 70, 80, 80, 80, 90, 100]
 
position = bisect.bisect_left(scores, 80)
print(position)   # 2
 
position = bisect.bisect_right(scores, 80)
print(position)   # 5

The list has three 80s at indices 2, 3, and 4. bisect_left(scores, 80) returns 2, the index before the first 80. bisect_right(scores, 80) returns 5, the index after the last 80.

Finding insertion points

bisect_left and bisect_right (aliased as bisect) find where a value belongs in a sorted list without actually inserting it, which is useful whenever you just need the position rather than a modified list.

python

import bisect
 
grades = ["A", "B", "B", "C", "D", "F"]
 
print(bisect.bisect_left(grades, "B"))    # 1
print(bisect.bisect(grades, "B"))          # 3
print(bisect.bisect_left(grades, "E"))    # 5

bisect is an alias for bisect_right. Use bisect_left when you want to insert before existing equal values (stable insertion order). Use bisect_right when you want to insert after them.

For values not in the list, both functions return the same index: the position where the value belongs.

Inserting into sorted lists

insort_left and insort_right insert a value into a sorted list in place, maintaining sorted order.

python

import bisect
 
data = [10, 20, 30, 40]
 
bisect.insort_left(data, 25)
print(data)   # [10, 20, 25, 30, 40]
 
bisect.insort_left(data, 30)
print(data)   # [10, 20, 25, 30, 30, 40]

insort_left(data, 25) inserts 25 between 20 and 30. insort_left(data, 30) inserts before the existing 30. The insertion itself is O(n) because Python must shift elements after the insertion point, but finding the insertion point is O(log n).

Practical uses for bisect

Grade boundaries. Map numeric scores to letter grades using a list of score thresholds.

python

import bisect
 
cutoffs = [60, 70, 80, 90]
grades = ["F", "D", "C", "B", "A"]
 
def letter_grade(score):
    return grades[bisect.bisect_right(cutoffs, score)]
 
for score in [55, 72, 88, 95]:
    print(f"{score} -> {letter_grade(score)}")

Each score is mapped to its letter grade by finding where it falls among the cutoffs, so a 72 lands between the 70 and 80 thresholds and earns a C:

text

55 -> F
72 -> C
88 -> B
95 -> A

bisect_right(cutoffs, 72) returns 2, and grades[2] is "C". The approach works for any mapping from continuous values to discrete buckets.

Search suggestions. Find words near a prefix in a sorted word list.

python

import bisect
 
words = sorted(["python", "pyramid", "pyre", "puzzle", "quartz", "query"])
 
def suggest(prefix, max_results=5):
    start = bisect.bisect_left(words, prefix)
    results = []
    for word in words[start:]:
        if not word.startswith(prefix):
            break
        results.append(word)
        if len(results) >= max_results:
            break
    return results

With the function defined, call it against a couple of prefixes to see how it collects matching words up to the max_results limit:

python

print(suggest("py"))
print(suggest("qu"))

Both calls land on the alphabetical starting point for their prefix and then walk forward only as long as words keep matching:

text

['pyramid', 'pyre', 'python']
['quartz', 'query']

bisect_left finds the first word that is alphabetically >= the prefix. Then the loop collects words that start with the prefix. This is the core of autocomplete suggestions.

Maintaining a sorted collection

Using insort to keep a list sorted as elements arrive:

python

import bisect
import random
 
sorted_list = []
for _ in range(10):
    value = random.randint(1, 100)
    bisect.insort(sorted_list, value)
 
print(sorted_list)

Ten random values are inserted one at a time, and the final list comes out fully sorted without a separate sort step at the end:

text

[3, 12, 15, 24, 37, 52, 58, 71, 84, 96]

Each insertion keeps the list sorted. For high-throughput scenarios where many insertions happen, consider heapq (priority queues) or a balanced tree structure for better performance.

bisect with custom key

bisect does not support a key argument directly, but you can use the "decorate-sort-undecorate" pattern:

python

import bisect
 
students = [
    (78, "Priya"),
    (85, "Devin"),
    (92, "Maya"),
]
 
def insert_by_score(students, name, score):
    index = bisect.bisect_left(students, score, key=lambda x: x[0])
    students.insert(index, (score, name))
 
insert_by_score(students, "Raj", 88)
print(students)

Raj's score of 88 places him between Devin and Maya, and the list stays sorted by score after the insertion:

text

[(78, 'Priya'), (85, 'Devin'), (88, 'Raj'), (92, 'Maya')]

The key parameter was added in Python 3.10 and allows bisect to extract the comparison key from each element in the list. Note that key only applies to elements already in the list; the search value itself (score here) must already be in the same "key space," which is why it is passed as a plain number rather than a full tuple.

Common mistakes

Using bisect on unsorted data. The binary search algorithm assumes ascending order. On an unsorted list, bisect returns an arbitrary position. Always sort first: data.sort().

Expecting O(log n) insertion with insort. Finding the insertion point is O(log n), but inserting into a Python list is O(n) because elements after the insertion point are shifted. For frequent insertions into a sorted structure, consider bisect + list only when reads dominate writes.

Using bisect for membership testing. bisect_left(data, x) is O(log n) but x in set(data) is O(1). For pure membership checks, use a set. Use bisect when you need the position, not just a boolean.

Confusing left and right for duplicate handling. If duplicates exist and you want stable insertion (new item before old ones), use insort_left. If you want new items after old ones, use insort_right.