Keeping a list ordered may look easy: append a new item and call sort(). That approach is acceptable for small collections or rare updates, but it repeats work when values arrive continuously and the application needs range queries, neighbors, or insertion positions. Python bisect solves this problem with binary search. It finds the correct position in an already sorted sequence without scanning every element.
This guide explains bisect_left(), bisect_right(), insort(), record searches with key, precomputed keys, range queries, duplicates, performance limits, and thread safety. It complements the guides about Python sort versus sorted, Python lists, Python functions, the collections module, and algorithms in programming.
What is the bisect module?
The bisect module implements a bisection algorithm for locating positions in sorted lists. Instead of comparing the target with every item, binary search checks the middle of the current range, discards half of the remaining positions, and repeats. Finding an insertion point therefore costs O(log n).
The official Python bisect documentation emphasizes that these functions locate insertion points. They do not call __eq__() to decide whether a value was found. They use ordering comparisons and return an index between existing values. This behavior is ideal for insertions, boundary searches, and range calculations.
The list must already be sorted
The most important requirement is that the sequence must be sorted with the same rule used by the search. If the data is unsorted, the returned index may be a valid integer but its meaning is unreliable.
from bisect import bisect_left
numbers = [3, 8, 12, 19, 25]
index = bisect_left(numbers, 15)
print(index) # 3
print(numbers[:index])
print(numbers[index:])The result says that 15 should be inserted before 19 at index 3. The function does not modify the collection; it only calculates a position.
bisect_left and bisect_right
The difference matters when equal values are already present. bisect_left() returns the position before the first equal item. bisect_right(), also exposed as bisect(), returns the position after the last equal item.
from bisect import bisect_left, bisect_right
values = [10, 20, 20, 20, 30]
start = bisect_left(values, 20)
end = bisect_right(values, 20)
print(start) # 1
print(end) # 4
print(values[start:end])Together, the two functions identify the complete range occupied by duplicates. The number of occurrences is end - start. The same technique works for timestamps, prices, scores, versions, and any consistently ordered key.
Searching for an exact value
Because bisect_left() returns an insertion point even when the target is absent, check the element at the returned position before declaring success.
from bisect import bisect_left
def find_index(values, target):
index = bisect_left(values, target)
if index != len(values) and values[index] == target:
return index
raise ValueError(f"{target!r} not found")
print(find_index([2, 5, 9, 14], 9))A dictionary or set is usually better for a large number of exact membership queries. bisect becomes especially valuable when order, nearest neighbors, and interval boundaries matter.
Inserting with insort
insort_left() and insort_right() combine position lookup with list.insert(). The left version inserts before equal values, while the right version inserts after them.
from bisect import insort
queue = [4, 9, 15, 22]
insort(queue, 12)
insort(queue, 9)
print(queue)Using append() would break ordering whenever the new item was not greater than the final element. Sorting the entire list after each insertion would also work, but it would repeat comparisons that binary search can avoid.
The real cost of insertion
Binary search takes O(log n), but inserting into the middle of a Python list takes O(n) because later references must be shifted. Therefore, insort() is convenient for frequent searches and a moderate number of updates, but it does not turn a list into a logarithmic-insertion data structure.
For millions of random updates, consider a balanced tree, an indexed database, or a dedicated sorted-collection library. If values arrive in increasing order, plain append() remains simpler and faster. The official Python data structures tutorial provides additional context about list, stack, queue, dictionary, and set behavior.
Restricting the search with lo and hi
The lo and hi parameters limit the search to part of a sequence. They are useful when another operation has already identified a relevant section.
from bisect import bisect_left
data = [2, 5, 8, 11, 14, 17, 20]
index = bisect_left(data, 13, lo=2, hi=6)
print(index)The bounds follow slice conventions: lo is included and hi is excluded. Use them only when the selected region still follows the same ordering rule.
Searching records with key
Since Python 3.10, bisect functions accept a key argument. The function extracts the comparison key from each stored record. During a search, the key function is not applied to the target x; the caller supplies the target key directly.
from bisect import bisect_left
from operator import itemgetter
products = [
{"name": "Notebook", "price": 18.0},
{"name": "Mouse", "price": 65.0},
{"name": "Keyboard", "price": 120.0},
]
by_price = itemgetter("price")
index = bisect_left(products, 70.0, key=by_price)
print(products[index]["name"])The records must already be sorted with the same key function. Sorting by name and searching by price violates the binary-search contract, even if the code runs without an exception.
Inserting records with key
With the insort functions, the key is applied to the new item during the search step, while the full object is inserted into the list.
from bisect import insort
from operator import itemgetter
tasks = [
{"priority": 1, "title": "Restore service"},
{"priority": 3, "title": "Generate report"},
]
new_task = {"priority": 2, "title": "Reply to customer"}
insort(tasks, new_task, key=itemgetter("priority"))
print([task["priority"] for task in tasks])Choose between left and right insertion deliberately when duplicate keys occur. If insertion order must be preserved, include a monotonically increasing sequence number in the record or comparison key.
Precomputing keys
Bisect search functions are stateless and discard key results. In a loop, an expensive key function may be called repeatedly for the same records. One solution is to keep a parallel list of precomputed keys.
from bisect import bisect_left
customers = [
("Ana", 1200),
("Bruno", 2500),
("Carla", 4100),
]
balances = [customer[1] for customer in customers]
index = bisect_left(balances, 3000)
print(customers[index])Whenever records are inserted or removed, update both lists as one logical operation. Another option mentioned by the documentation is wrapping a pure, expensive key function with functools.cache().
Range queries
A common task is selecting every value between two inclusive limits. Use bisect_left() for the lower boundary and bisect_right() for the upper boundary.
from bisect import bisect_left, bisect_right
temperatures = [12, 15, 18, 18, 21, 24, 27, 30]
start = bisect_left(temperatures, 18)
end = bisect_right(temperatures, 24)
print(temperatures[start:end])Locating both boundaries costs O(log n). Building the slice costs time and memory proportional to the number of returned elements. When only a count is needed, calculate end - start and avoid copying the records.
Classifying values into intervals
bisect() can map sorted thresholds to categories. The returned index selects the matching bucket.
from bisect import bisect
breakpoints = [60, 70, 80, 90]
grades = "FDCBA"
def grade(score):
return grades[bisect(breakpoints, score)]
print(grade(77))
print(grade(90))The same pattern supports tax brackets, risk levels, package sizes, pricing tiers, and service-level rules. Document whether a boundary belongs to the previous or next interval, because that decision determines whether left or right bisection is correct.
Finding neighboring values
The insertion index also gives access to the closest values around a target. After bisect_left(values, x), the item at index - 1 is the greatest value below x, when such an item exists. The item at index is the first value greater than or equal to x.
from bisect import bisect_left
times = [8, 10, 13, 16, 19]
index = bisect_left(times, 14)
previous = times[index - 1] if index else None
following = times[index] if index != len(times) else None
print(previous, following)This technique is useful for calendars, time series, software versions, sensor readings, and geographic or financial breakpoints.
Building reusable lookup helpers
Application code becomes clearer when common boundary rules are wrapped in named functions. A helper can return the first value greater than or equal to a target, while another can return the last value below it.
from bisect import bisect_left, bisect_right
def find_ge(values, target):
index = bisect_left(values, target)
if index != len(values):
return values[index]
raise ValueError("no value is large enough")
def find_lt(values, target):
index = bisect_left(values, target)
if index:
return values[index - 1]
raise ValueError("no value is smaller")Clear helper names reduce off-by-one mistakes and make inclusive or exclusive behavior visible to reviewers and test authors.
bisect, dictionaries, sets, or heaps?
Choose bisect when sorted order matters and the application needs ranges, neighbors, or insertion positions. Choose a dictionary or set for high-volume exact lookup. Choose heapq when the main operation is repeatedly removing the smallest or largest item rather than searching arbitrary positions.
An indexed database is a better fit when the data exceeds memory, requires persistence, or receives concurrent updates. The correct choice depends on the complete read-and-write pattern, not only on the theoretical complexity of one search operation.
Thread safety
The bisect functions are not thread-safe when multiple threads operate on the same sequence. If one thread mutates the list while another searches or inserts, the sorted invariant may be lost and behavior is undefined. Protect the complete operation with a lock or use separate structures per worker.
Locking only the call to bisect() and releasing the lock before insert() is insufficient. Another thread could change the collection between those steps. Position lookup and insertion must be one critical section.
Common mistakes
- Calling bisect on an unsorted list.
- Sorting records with one key and searching with another.
- Treating the returned index as proof that the value exists.
- Ignoring the difference between left and right insertion.
- Expecting
O(log n)insertion into an ordinary list. - Recomputing an expensive key during thousands of searches.
- Mutating the same list concurrently without synchronization.
Testing sorted searches
Test boundary conditions: an empty list, a value smaller than all items, a value larger than all items, duplicate values, and exact boundaries. Also verify that repeated insertions preserve sorting.
from bisect import insort
def test_insertions_preserve_order():
values = []
for number in [9, 2, 7, 7, 1]:
insort(values, number)
assert values == [1, 2, 7, 7, 9]Range helpers should include cases with no matches, one match, duplicate boundaries, and every item inside the interval. These tests expose off-by-one errors quickly.
Best practices
- Centralize searches and insertions in small functions.
- Document the ordering rule and duplicate policy.
- Use a key function consistent with the original sort.
- Precompute keys when extraction is expensive.
- Avoid creating slices when only a count is required.
- Benchmark large insertion workloads before choosing a list.
- Protect the complete operation under concurrency.
Conclusion
Python bisect turns sorted lists into efficient structures for locating insertion points, boundaries, and neighboring values. bisect_left and bisect_right define duplicate behavior, while insort preserves order after new entries. The key argument extends the same technique to tuples, dictionaries, and custom objects.
Search is logarithmic, but list insertion remains linear. The module is therefore an excellent choice for read-heavy workflows with a moderate number of updates. When scale, concurrency, or persistence requirements grow, another structure may be more appropriate. With a documented ordering contract and strong boundary tests, bisect remains simple, predictable, and powerful.
