Python Basics: Searching Sorted Lists with bisect

Python’s bisect module finds where a value belongs in an already sorted list. It helps locate duplicate ranges and insert new records without sorting everything again.

Use Python 3.12 or newer on Linux. These independent examples use only in-memory data.

Find the boundaries of repeated values

Save as demo_bisect_1.py:

from bisect import bisect_left, bisect_right

scores = [10, 20, 20, 20, 30]
left = bisect_left(scores, 20)
right = bisect_right(scores, 20)
print("Positions:", left, right)
print("Matches:", scores[left:right])
print("Count:", right - left)

Run it from the directory where you saved it:

python3 demo_bisect_1.py

Output:

Positions: 1 4
Matches: [20, 20, 20]
Count: 3

The left boundary comes before equal values; the right boundary comes after them. Both positions are zero-based. bisect does not sort or validate your input: keep it sorted in ascending order under the comparison you use.

Check whether a value exists

Save as demo_bisect_2.py:

from bisect import bisect_left

numbers = [4, 8, 12]
for target in (8, 9, 20):
    index = bisect_left(numbers, target)
    found = index < len(numbers) and numbers[index] == target
    print(f"{target}: position={index}, found={found}")

Run it from the directory where you saved it:

python3 demo_bisect_2.py

Output:

8: position=1, found=True
9: position=2, found=False
20: position=3, found=False

An insertion position alone does not prove that the value exists. Check the bounds before indexing, then check equality. The and expression skips the second check when the index is past the end. This also handles an empty list safely.

Insert records using a key

Save as demo_bisect_3.py:

from bisect import bisect_left, insort_right
from operator import itemgetter

jobs = [(10, "backup"), (30, "report")]
by_minute = itemgetter(0)
print("Position for 20:", bisect_left(jobs, 20, key=by_minute))
insort_right(jobs, (20, "cleanup"), key=by_minute)
insort_right(jobs, (20, "archive"), key=by_minute)
for minute, name in jobs:
    print(minute, name)

Run it from the directory where you saved it:

python3 demo_bisect_3.py

Output:

Position for 20: 1
10 backup
20 cleanup
20 archive
30 report

For bisect_left(), pass the comparison key as the search value: 20 here. For insort_right(), pass the whole record; it calculates the new record’s key and inserts after existing ties. Insertion modifies the list. Searching takes O(log n) comparisons, but shifting list elements makes insertion O(n).

References

• Python bisect documentation

Acknowledgements

This post was created with assistance from AI.