Python bisect key: search with a key value, insert with a record

Observed contract

A due-date index stores receipt records ordered by day. The search passes day 47, rather than an entire record, to bisect_left. insort_left then receives a full new record and places it at the correct day.

Boundary

Bisection assumes the list remains sorted under the same key. Mutating a stored record's day breaks later searches. Concurrent writers also need synchronization around search and insertion; the functions do not make a shared list transactional.

Executable case

from bisect import bisect_left, insort_left

receipts = [
    {"due_day": 12, "receipt": "R-12"},
    {"due_day": 47, "receipt": "R-47"},
    {"due_day": 73, "receipt": "R-73"},
]
due_day = lambda receipt: receipt["due_day"]
print("found_at", bisect_left(receipts, 47, key=due_day))
insort_left(receipts, {"due_day": 26, "receipt": "R-26"}, key=due_day)
print("ordered_days", [receipt["due_day"] for receipt in receipts])

Output

found_at 1
ordered_days [12, 26, 47, 73]

Cost

The search uses O(log n) comparisons, but insertion shifts list entries and costs O(n). Computing an expensive key repeatedly can dominate comparisons; keep precomputed keys when queries are frequent.

Common Mistakes

• For bisect_left with key, pass the search key as x, not a full record.
• Do not mutate an indexed sort field in place.
• A log-time search does not make list insertion log-time.

Connected lessons

• Python bisect: binary position search does not make list insertion logarithmic
• Python sorting: stable keys, independent output and explicit tie rules
• Python binary search on capacity: prove the feasibility predicate

Test this contract.