The bisect module uses binary search to locate positions in sorted lists. It finds insertion points without scanning every element and provides insort() helpers that preserve ordering after insertion. It is useful for small or medium in-memory indexes, ranges, rankings, calendars, and algorithms that receive data incrementally.
Searching costs O(log n), but inserting into a list remains O(n) because later references must move. bisect is therefore strongest when searches are frequent and insertions are moderate. For heavy update workloads, trees, databases, or specialized containers may be more appropriate.
The list must already be sorted
The functions do not verify the precondition.
from bisect import bisect_left
values = [10, 20, 30, 40]
position = bisect_left(values, 25)
print(position)
If the sequence uses a different ordering rule or is unsorted, the result is not reliable.
bisect_left
bisect_left() returns the position before existing equal values.
values = [10, 20, 20, 20, 30]
print(bisect_left(values, 20))
Use it to find the first occurrence or insert before duplicates.
bisect_right
bisect_right(), also exposed as bisect(), returns the position after equal values.
from bisect import bisect_right
print(bisect_right(values, 20))
Use it when new equal items should follow existing ones.
Locate all duplicates
The left and right positions delimit every equal element.
start = bisect_left(values, target)
end = bisect_right(values, target)
equal_items = values[start:end]
The slice copies references. Keep the indexes when a copy is unnecessary.
insort_left and insort_right
These functions find the position and insert the value.
from bisect import insort_left
insort_left(values, 25)
The search is logarithmic, but moving list elements is still linear.
Do not sort after every append
insort() avoids sorting the entire list after each new item.
When many new values are already available, extending the list and sorting once is usually better.
Exact lookup
bisect returns positions rather than a direct exact-match function.
def find_index(items, value):
index = bisect_left(items, value)
if index != len(items) and items[index] == value:
return index
raise ValueError("value was not found")
Check the boundary before indexing.
Find the closest lower value
def lower_than(items, value):
index = bisect_left(items, value)
if index:
return items[index - 1]
raise ValueError("no lower value")
Similar helpers can implement lower-or-equal, higher-or-equal, and strictly higher queries.
Classify numeric ranges
A sorted list of thresholds can map values to labels.
breaks = [0, 10, 20, 50]
labels = ["negative", "low", "medium", "high", "very high"]
category = labels[bisect_right(breaks, number)]
Test values exactly on each threshold to confirm the inclusion rule.
The key parameter
Modern Python versions allow a key function for elements in the sorted sequence.
records = [
{"id": 1, "name": "A"},
{"id": 5, "name": "B"},
]
position = bisect_left(records, 3, key=lambda item: item["id"])
The searched value is compared against extracted keys; it is not automatically transformed in the same way. Follow the API of the project’s minimum Python version.
Cache expensive keys
An expensive key function may run repeatedly during binary searches.
Maintain a parallel list of keys or cache results when records are immutable. Update both sequences atomically.
ids = [item.id for item in records]
position = bisect_left(ids, new.id)
ids.insert(position, new.id)
records.insert(position, new)
Composite tuple keys
Tuples use lexicographic ordering.
events = [(10, 1, "a"), (10, 2, "b"), (20, 1, "c")]
position = bisect_right(events, (10, float("inf"), ""))
Avoid non-comparable payloads after fields that may tie. A unique sequence number is safer.
Dates and times
Compatible datetime objects can be ordered, but mixing timezone-aware and naive values raises errors.
Normalize timezones and define how equal timestamps should be ordered.
Rankings
For an ascending ranking, bisect_left() gives the insertion position. For descending order, use negative keys or maintain one clear ordering rule.
Heavy score updates can make list insertion too expensive.
Approximate percentile use
A sorted list provides quantile values by index, but storing every observation may consume substantial memory.
Large streams may need approximate quantile algorithms.
Do not mutate during a search
The functions are not safe if another thread changes the sequence concurrently.
Protect lookup and insertion with the same lock or operate on immutable snapshots.
Search and insertion must be atomic
Calculating a position and inserting later allows another writer to invalidate the position.
with lock:
position = bisect_left(values, new_value)
values.insert(position, new_value)
insort() combines the steps, but shared access still requires synchronization.
NaN and total ordering
float('nan') has unusual comparison behavior and does not participate in a normal total order.
Filter or normalize NaN before maintaining a sorted numeric list.
Mutable sort keys
If a field used for ordering changes after insertion, the list becomes unsorted.
Remove and reinsert the record, or use immutable key objects.
Real complexity
Binary search performs few comparisons, but insertion shifts references. On large lists, movement dominates the cost.
Benchmark with the real read-to-write ratio.
bisect versus heapq
heapq is better when repeatedly removing the minimum. bisect is better for ordered indexing, range queries, and neighbors.
See Python heapq.
bisect versus set and dict
For existence checks alone, set and dict usually provide average O(1) lookup.
Choose bisect when order, positions, or intervals matter.
Persistence
Validate or sort data after loading it from storage. Do not assume an external file remains ordered.
For very large indexes, a database may be more appropriate.
Security
Limit the number of externally supplied items. An unbounded sorted list can exhaust memory and make every insertion slower.
Validate keys and avoid comparison functions with side effects.
Testing
Test empty lists, one item, duplicates, boundaries, values below and above all entries, composite keys, NaN, updates, and concurrency.
Check the invariant items == sorted(items) after operation sequences.
Common mistakes
Common failures include using an unsorted list, confusing left and right, forgetting linear insertion cost, mutating keys in place, misunderstanding key, ignoring NaN, and separating lookup and insertion without a lock.
Conclusion
bisect provides binary search and ordered insertion through a small API. It fits in-memory sequences with many lookups and a moderate number of updates.
Choose left or right deliberately, preserve one ordering rule, and synchronize concurrent changes. Consult the official bisect documentation and Python heapq.
