Binary Search with bisect
Published by Brayan K
The bisect module performs binary search on a sorted list: it finds in O(log n) time exactly where a value belongs, so you can locate items, look up grade boundaries, or insert while keeping the list sorted — without ever re-sorting.
Part of the free Python course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.
An insertion position is not proof that a value exists
bisect_left returns a boundary in an already sorted list. That boundary is useful whether the value exists or not. It can equal the list length when the target belongs after every stored value. Treating the return value as a found index can therefore report the wrong record or raise an error.
from bisect import bisect_left
readings = [10, 20, 20, 40]
for target in [5, 20, 30, 50]:
position = bisect_left(readings, target)
found = position < len(readings) and readings[position] == target
print(target, position, found)
# ✅ Expected output:
# 5 0 False
# 20 1 True
# 30 3 False
# 50 4 FalseThe length check comes first so the equality test is skipped at the end boundary. This distinguishes absent values before, between and after existing entries. Bisection does not sort the input or verify its ordering. If arrivals have been appended out of order, restore the ordering before searching; Sorting with sorted() & key covers that step.
from bisect import bisect_left
readings = [10, 20, 40]
position = bisect_left(readings, 50)
print(readings[position])
# ✅ Expected error:
# IndexError: list index out of rangeDuplicate values have a left edge and a right edge
from bisect import bisect_left, bisect_right
readings = [10, 20, 20, 20, 40]
left = bisect_left(readings, 20)
right = bisect_right(readings, 20)
print("Bounds:", left, right)
print("Count:", right - left)
print("Equal range:", readings[left:right])
# ✅ Expected output:
# Bounds: 1 4
# Count: 3
# Equal range: [20, 20, 20]The left boundary goes before all equal values; the right boundary goes after them. Subtracting the positions gives their count. The same boundaries can select a half-open interval: left boundaries for both limits include the lower limit and exclude the upper limit. List slicing follows the same exclusive-end rule, explained in Slicing Lists & Strings.
from bisect import bisect_left
readings = [10, 20, 20, 30, 40, 50]
start = bisect_left(readings, 20)
stop = bisect_left(readings, 40)
print(readings[start:stop])
# ✅ Expected output:
# [20, 20, 30]Fast searching does not make list insertion logarithmic
The search uses logarithmically many comparisons. Inserting into a Python list may shift many later entries, making insort linear overall. Finding where a value belongs and making room for it are separate operations. For a small changing list, the simple implementation can still be a good choice.
from bisect import insort_right
readings = [10, 20, 40]
returned = insort_right(readings, 30)
print(readings)
print("Return value:", returned)
# ✅ Expected output:
# [10, 20, 30, 40]
# Return value: NoneThe operation changes the existing list and returns None. For many arrivals at once, extending then sorting can be simpler than performing a separate insertion for every item. Avoid promising a universal speedup: list size, comparison cost and update patterns matter. Bisection is most compelling when ordered range lookups are useful between updates.
A search key transforms stored records, not the search value
Suppose records are sorted by their score. With key, a bisection search applies the key function to stored records. Supply the target score directly. In contrast, insort_right accepts the complete new record, applies the key while locating its position, and inserts that original record.
from bisect import bisect_left, insort_right
records = [(10, "Asha"), (20, "Ben"), (20, "Cleo")]
score = lambda record: record[0]
position = bisect_left(records, 20, key=score)
print("First score match:", records[position])
insort_right(records, (20, "Dara"), key=score)
print(records)
# ✅ Expected output:
# First score match: (20, 'Ben')
# [(10, 'Asha'), (20, 'Ben'), (20, 'Cleo'), (20, 'Dara')]Right insertion places Dara after the existing score ties. Left insertion would place Dara before them. Keep the list sorted by the same key used by the search; changing a stored score in place can invalidate that assumption without raising an exception.
from bisect import bisect_left
records = [(10, "Asha"), (20, "Ben")]
bisect_left(records, (20, "Dara"), key=lambda record: record[0])
# ✅ Expected error:
# TypeError: '<' not supported between instances of 'int' and 'tuple'Find a count without treating zero as failure
Complete the lower and upper boundaries for score 10. Then check target 25 for exact membership using a guarded equality test. Index zero is a valid boundary, so if position: is not a membership test.
from bisect import bisect_left, bisect_right
scores = [10, 10, 20, 30]
left = ___(scores, 10)
right = ___(scores, 10)
position = bisect_left(scores, 25)
found = position < len(scores) and scores[position] == ___
print("Count:", right - left)
print("Found:", found)
# 👉 replace ___ with bisect_left
# 👉 replace ___ with bisect_right
# 👉 replace ___ with 25
# ✅ Expected output:
# Count: 2
# Found: FalseBuild an inclusive range report after an arrival
Start with sorted measurements 12, 18, 18, 27 and 35. Insert a new 27. Report all measurements from 18 through 27 inclusive, then print how many 27s are stored. Finally check whether 99 is present, safely handling a boundary at the list end. Do not scan every element to compute these boundaries.
from bisect import bisect_left, bisect_right, insort_right
measurements = [12, 18, 18, 27, 35]
insort_right(measurements, 27)
start = bisect_left(measurements, 18)
stop = bisect_right(measurements, 27)
print("Range:", measurements[start:stop])
print("Count of 27:", bisect_right(measurements, 27) - bisect_left(measurements, 27))
position = bisect_left(measurements, 99)
print("Has 99:", position < len(measurements) and measurements[position] == 99)
# ✅ Expected output:
# Range: [18, 18, 27, 27]
# Count of 27: 2
# Has 99: FalseThe right boundary includes every value equal to the upper limit. Both the range and count reuse the sorted-order assumption. If that assumption stops being true after an edit, these answers are no longer trustworthy.
Practice quiz
What does this program print? from bisect import bisect_left a = [10, 20, 40] print(bisect_left(a, 30))
- -1
- True
- 3
- 2
Answer: 2. The returned boundary is where 30 belongs, even though it is absent.
What does this program print? from bisect import bisect_left, bisect_right a = [1, 2, 2, 2, 4] print(bisect_left(a, 2), bisect_right(a, 2))
- 1 3
- 1 4
- 2 4
- 0 5
Answer: 1 4. The left boundary precedes all ties and the right boundary follows them.
What does this program print? from bisect import bisect_left a = [1, 3] i = bisect_left(a, 8) print(i < len(a) and a[i] == 8)
- False
- True
- 2
- IndexError: list index out of range
Answer: False. Short-circuiting avoids indexing beyond the list.
What is the overall worst-case time of inserting into a list with insort?
- O(1)
- O(log n)
- O(n)
- O(n²)
Answer: O(n). The linear shifting step dominates the logarithmic search.
What does this program print? from bisect import bisect_left a = [(10, "A"), (20, "B")] print(bisect_left(a, 20, key=lambda row: row[0]))
- 0
- 1
- 2
- TypeError
Answer: 1. The target is already a score; only stored rows need key extraction.
What does this program print? from bisect import insort_right a = [(10, "A"), (10, "B")] insort_right(a, (10, "C"), key=lambda row: row[0]) print([row[1] for row in a])
- ['C', 'A', 'B']
- ['A', 'C', 'B']
- ['A', 'B']
- ['A', 'B', 'C']
Answer: ['A', 'B', 'C']. Right insertion follows the existing equal-key entries.
What does this program print? from bisect import bisect_left, bisect_right a = [1, 2, 2, 3, 4] print(a[bisect_left(a, 2):bisect_right(a, 3)])
- [2, 2]
- [2, 3]
- [2, 2, 3]
- [1, 2, 2, 3]
Answer: [2, 2, 3]. The right boundary for 3 includes that upper endpoint.
What must be true before bisection can give meaningful boundaries?
- The list is sorted by the ordering used in the search
- The values are unique
- The list contains the target
- The list has an even length
Answer: The list is sorted by the ordering used in the search. Bisection assumes sorted input and does not validate or repair it.
Continue this course
- Previous: Heaps with heapq (Priority Queues)
- Next: Numbers: int, float, Decimal & Fraction — Exact money math with Decimal, exact ratios with Fraction, and float pitfalls
- Quick reference: Python cheat sheet