Incremental ordered insertion
Maintain a sorted in-memory collection as records arrive.
Python · Module
bisect
The bisect module finds insertion points in sorted sequences and provides helpers for inserting values without resorting the list. Left and right variants control whether duplicates are placed before or after existing equal values.
How it works
The module locates insertion points in an already sorted sequence using comparisons, then optionally inserts through list operations. Left variants place an equal value before existing equals; right variants place it after them. Bounds can restrict the search to a slice, and key functions can define the ordering for supported APIs.
Syntax
bisect_left(a, x, lo=0, hi=len(a), *, key=None)
bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect(a, x, lo=0, hi=len(a), *, key=None)
insort_left(a, x, lo=0, hi=len(a), *, key=None)
insort_right(a, x, lo=0, hi=len(a), *, key=None)
insort(a, x, lo=0, hi=len(a), *, key=None)Parameters
| Name | Type | Description |
|---|---|---|
a | sequence/list | Sorted sequence being searched or modified. |
x | value | Value whose insertion position is located or which is inserted. |
lo | int | Lower bound of the search range; defaults to 0. |
hi | int | Upper bound of the search range; defaults to len(a). |
key | callable | None | Optional ordering function for supported modern APIs. |
Returns
The bisect search functions return an integer insertion index; insort functions modify the list in place and return None.
Key points
- Use bisect when maintaining sorted order incrementally is preferable to repeatedly sorting the whole list.
- The core operations return positions, making them useful for lower-bound and upper-bound searches.
- Ordering is determined through less-than comparisons rather than equality checks.
- Pass lo and hi to limit the search to a sorted interval instead of the entire list.
- The right-biased operation places duplicates after the existing equal values.
- insort operations combine position lookup with insertion into the mutable list.
Common mistakes
- These functions locate insertion positions rather than testing equality, so custom ordering must work correctly with less-than comparisons.
- Use the left variant when equal values must be inserted before the existing equal range.
Example: Find and insert in a sorted list
from bisect import bisect_left, insort
scores = [10, 20, 20, 40]
position = bisect_left(scores, 20)
insort(scores, 25)
print(position, scores)Finds the first valid position for 20, then inserts 25 while preserving sorted order.
When to use it
Range and duplicate queries
Locate the lower or upper boundary of a value range.
Bounded interval lookup
Restrict searching to a known sorted section.
Interview questions
QWhat does bisect_left return?
bisect_left returns the first position where x can be inserted while keeping the list sorted. Equal elements remain at or after that position, so it is useful for lower-bound searches.
Follow-up: How do you find whether x exists? Compute i = bisect_left(a, x), then check i < len(a) and a[i] == x.
QHow does bisect differ from bisect_left?
bisect_right, also exposed as bisect, returns a position after existing entries equal to x. This makes it the upper bound of x in the sorted range.
Follow-up: How can it count equal values? Subtract bisect_left(a, x) from bisect_right(a, x).
QWhat is the performance trade-off when using insort?
The bisect search is logarithmic, but list insertion is linear because later elements must move. Therefore, repeated insertions can be costly for large lists.
Follow-up: What alternative fits frequent ordered insertions? The documentation points to sorted collections as an alternative; a tree-based structure can avoid array shifting.
Related
bisect_leftbisect_rightbisectinsort_leftinsort_rightinsort