Python bisect vs insort: Boundaries, Keys and 8 Tested Examples

bisect finds a position; insort inserts an item. Both assume the searched data is already sorted under the same ordering rule. bisect_left returns the boundary before equal values and bisect_right the boundary after them. Neither result alone proves that the target exists. These eight tested Python examples cover duplicates, exact lookup, range counts, records with key and insertion costs.

The numeric examples use ordinary ascending integers. The key examples need Python 3.10 or later. They are single-threaded: Python's bisect documentation warns that concurrent use on the same sequence, or mutation during a search, is unsafe.

1. Compare bisect and insort

Function	Returns	Changes list?	Equal-key position
bisect_left(a,x)	Insertion index	No	Before existing equals
bisect_right(a,x)	Insertion index	No	After existing equals
insort_left(a,x)	None	Yes	Before existing equals
insort_right(a,x)	None	Yes	After existing equals

bisect is an alias for bisect_right; insort is an alias for insort_right. Binary search does not sort an unsorted list. The returned insertion index can be 0 or len(a), because there are n+1 gaps around n items. Search and insertion are different operations, even when one function combines them.

2. Trace the duplicate boundaries

Boundaries are gaps, not Boolean found flags. The two equal 20 values occupy indices 1 and 2.

One way to understand bisect_left is to keep a half-open candidate window[lo,hi). If a[mid] < target, move lo to mid+1; otherwise move hi to mid. At termination lo == hi is the answer. For this example:

lo	hi	mid	a[mid]	Next window
0	4	2	20	[0,2)
0	2	1	20	[0,1)
0	1	0	10	[1,1), return 1

This is an explanatory algorithm trace, not a promise about a particular Python build's internal implementation. bisect_right returns 3 because it puts the insertion gap after the equal block.

3. Eight tested examples

Example 1: Left and right boundaries are not found flags

from bisect import bisect_left, bisect_right
values = [10, 20, 20, 40]
for target in [20, 25, 50]:
    print(target, bisect_left(values, target),
          bisect_right(values, target))
print(values)

Output

20 1 3
25 3 3
50 4 4
[10, 20, 20, 40]

For 20, the half-open equal-value block is values[1:3]. For 25, both boundaries are 3 although 25 is absent. For 50, the boundary is len(values), which is a legal insertion position but not a legal element index. Neither search changes the list.

Example 2: insort mutates and returns None

from bisect import insort_left
values = [10, 20, 40]
result = insort_left(values, 30)
print(values)
print(result)

Output

[10, 20, 30, 40]
None

insort_left finds the position, then inserts the actual value. Do not assign values = insort_left(values,30): the name would become None. The search is logarithmic in comparisons on a list; moving elements for insertion can still take linear time.

Example 3: Exact membership needs a bounds and equality check

from bisect import bisect_left
def contains(values, target):
    i = bisect_left(values, target)
    return i < len(values) and values[i] == target
for values, target in [([], 5), ([10, 20], 20),
                       ([10, 20], 15), ([10, 20], 30)]:
    print(contains(values, target))

Output

False
True
False
False

Short-circuit and prevents indexing beyond the list or into an empty list. A returned position only describes an ordering boundary. The extra equality test turns that boundary into a membership answer for these ordinary integers.

Example 4: Count an inclusive numeric range with two boundaries

from bisect import bisect_left, bisect_right
values = [10, 20, 20, 30, 40]
low, high = 20, 30
left = bisect_left(values, low)
right = bisect_right(values, high)
print(left, right)
print(right - left)
print(values[left:right])
print(bisect_right(values, 20) - bisect_left(values, 20))

Output

1 4
3
[20, 20, 30]
2

Use left at the lower endpoint and right at the upper endpoint to include both. The interval has 3 values, including both 20 s. A count uses two logarithmic searches; creating the displayed slice additionally copies the selected k elements, so that display step costs O(k). Require low <= high or explicitly return 0 for an empty reversed interval.

Example 5: Predecessor and successor require edge checks

from bisect import bisect_left, bisect_right
values = [10, 20, 20, 40]
for target in [5, 20, 50]:
    left = bisect_left(values, target)
    right = bisect_right(values, target)
    previous = values[left - 1] if left > 0 else None
    following = values[right] if right < len(values) else None
    print(target, previous, following)

Output

5 None 10
20 10 40
50 40 None

Here predecessor means strictly smaller, and successor means strictly greater. bisect_left minus 1 skips equal values on the left; bisect_right skips equals on the right. For numeric data, None is a clear missing-result marker. Without left > 0, Python index-1 would wrap to the final item and return a false predecessor.

Example 6: With key, a search probe is already a key

from bisect import bisect_left
from operator import itemgetter
rows = [('Ada', 50), ('Bo', 70), ('Cy', 70), ('Di', 90)]
by_score = itemgetter(1)
i = bisect_left(rows, 70, key=by_score)
print(i)
print(rows[i])

Output

1
('Bo', 70)

The list is sorted by score. key transforms each stored row for comparison, but bisect_left does not transform the search target 70. Passing a full row as the probe would compare scores with a tuple and fail for this data. key support requires Python 3.10 or later.

Example 7: insort applies key to a new record, and ties have a side

from bisect import insort_left, insort_right
from operator import itemgetter
rows = [('Ada', 50), ('Bo', 70), ('Cy', 70), ('Di', 90)]
left = rows.copy()
right = rows.copy()
insort_left(left, ('Eve', 70), key=itemgetter(1))
insort_right(right, ('Eve', 70), key=itemgetter(1))
print([name for name, score in left])
print([name for name, score in right])
print([name for name, score in rows])

Output

['Ada', 'Eve', 'Bo', 'Cy', 'Di']
['Ada', 'Bo', 'Cy', 'Eve', 'Di']
['Ada', 'Bo', 'Cy', 'Di']

Unlike a bisect search probe, insort receives the full new record. It applies key to that record for the search, then inserts the record itself. left places Eve before existing score 70 records; right places Eve after them. Repeated right insertions retain arrival order within an equal-key block, provided the same ordering key is used throughout.

Example 8: lo and hi search only the chosen half-open window

from bisect import bisect_left, bisect_right
values = [10, 20, 20, 20, 40]
print(bisect_left(values, 20))
print(bisect_left(values, 20, lo=2, hi=4))
print(bisect_right(values, 20, lo=2, hi=4))
print(bisect_left([], 7))

Output

1
2
4
0

The restricted search sees indices 2 and 3 only, so its left boundary is 2, not the global boundary 1. lo is inclusive and hi exclusive. Use valid bounds 0 <= lo <= hi <= len(values). A sorted search window is not a promise that an insertion there preserves order outside the window. Use the full list unless a narrower range is justified.

4. Boundary formulas to revise

Let L = bisect_left(a,x) and R = bisect_right(a,x), searching the entire sorted numeric list. Equal values occupy a[L:R]. The number of occurrences is R-L, even when the target is absent or the list is empty.

Question	Candidate index	Required check
First value >= x	L	L < len(a)
First value > x	R	R < len(a)
Last value < x	L-1	L > 0
Last value <= x	R-1	R > 0
Exact occurrence	L	L < len(a) and a[L] == x

These formulas separate an ordering boundary from an actual element. With custom keys, the equal-key block can hold records that are not equal as whole objects. With unusual comparisons, including floating-point NaN, ordinary numeric-order assumptions may not hold. Do not use these examples as a generic equality search for every possible object.

5. Why insertion is still linear

On a Python list, bisection needs O(log n) comparisons. Inserting into the middle can shift O(n) references, so insort is O(n) overall for ordinary constant-cost comparisons. key computation or custom comparison can add its own cost. Repeating n insertions can therefore take O(n squared) total work in the worst case.

For a batch of new items, combining and sorting once may fit better. For exact membership without sorted range queries, consider a set or dictionary. For frequent sorted insertions at scale, reconsider the data structure rather than calling insort logarithmic. Choose from the actual workload, not the function name.

The search functions do not retain computed keys between calls. If a key is expensive, precomputing a parallel key list can help repeated searches, but every insertion, deletion and key-changing edit must keep the two lists aligned. A stale key list gives incorrect answers. The examples use a cheap key and avoid a second index to maintain.

6. Common mistakes and fixes

Mistake	Fix
Search an unsorted list	Sort with the same ordering rule first; do not expect bisect to validate it
Treat the index as found	Check bounds and equality for exact membership
Use a[i] when i == len(a)	A legal insertion gap can be past the last element
Use a[left-1] without checking left	Guard against negative-index wraparound
Pass a whole record to bisect with key	Pass the already-extracted target key
Pass only a key to insort of records	Pass the full record; key is used for its search step
Assume lo/hi produces global boundaries	The bounds describe only the selected window
Mutate ordering fields after insertion	Restore the ordering invariant before later searches

7. Practice and exam Q&A

Does bisect_left return True when a target exists?

No. It returns an insertion index before existing equal values. Exact membership needs a bounds check followed by equality.

What do left and right return for an absent integer?

They return the same insertion gap in a normally sorted integer list.

How do you count repeated x values?

Compute bisect_right(a,x)-bisect_left(a,x), using the same search range and ordering.

How do you include both endpoints of a numeric interval?

Use bisect_left(a,low) and bisect_right(a,high). Their difference is the count when low <= high.

Why is insort not O(log n)?

Its logarithmic search is followed by a possibly linear list insertion.

Can the answer equal len(a)?

Yes. That is the gap after the last item, not a valid element index.

Does key transform x in bisect_left?

No. It transforms stored elements. Pass an already-extracted key as the probe.

Does key transform a new record in insort?

For the search step, yes. The original record is then inserted without replacing it by its key.

Which insertion side preserves arrival order among ties?

Repeated insort_right calls append new equal-key records after older ones, as long as the ordering key stays consistent.

Can another thread safely mutate the same sequence during a search?

No. The official documentation warns that concurrent bisect use on the same sequence or mutation during a search is unsafe.

8. Revision tasks with answers

For a = [2,4,4,7], predict both boundaries for 4,5 and 1. Answers:4 gives(1,3),5 gives(3,3),1 gives(0,0). Count values in inclusive range[4,7]: right(7)-left(4) = 4-1 = 3. The slice is[4,4,7]. The strict predecessor of 2 is absent; do not let index-1 turn it into 7.

For records[('Bo',70),('Cy',70)], insert('Eve',70) by score. Left insertion gives Eve,Bo,Cy; right insertion gives Bo,Cy,Eve. Explain why searching those rows uses the number 70 but inserting uses the full tuple. Then test an empty list and a target larger than all values before trusting an indexing expression.

Final checklist: sorted input, consistent key, correct left/right side, valid half-open bounds, checked element access and realistic insertion cost. These conditions matter more than memorizing a function name.

Official source and related lessons

• Python bisect documentation: boundaries, key behavior, thread safety and performance

Continue with sorted vs list.sort and stable keys, binary search, or the Exam Notes hub. These are universal learning and exam-practice notes, not an official university syllabus or a predicted paper.