Python bisect: binary position search does not make list insertion logarithmic

Operation contract

The receipt amount list is ascending. Bisect_left finds the first position for an equal amount, while bisect_right finds the position after all equal amounts. Inserting at the right boundary retains the ordering. The fixture uses immutable integer values and an owned list so comparisons and mutation have a clear boundary.

Failure and ownership boundary

Bisect does not sort or validate an arbitrary input. A concurrent mutation can invalidate the selected position between search and insertion. Expensive keys may be recomputed, and comparisons need a coherent ordering policy. Python binary search: use a half-open interval and require sorted input and Python sorting: stable keys, independent output and explicit tie rules explain the prerequisite rather than assuming every list qualifies.

Working program

from bisect import bisect_left, bisect_right, insort_right

amounts = [75, 125, 125, 250]
print(bisect_left(amounts, 125), bisect_right(amounts, 125))
insort_right(amounts, 125)
print(amounts)
print("outside upper boundary:", bisect_right(amounts, 500))

Output

1 3
[75, 125, 125, 125, 250]
outside upper boundary: 5

Costs and limits

Position search makes O(log n) comparisons. Inserting into a Python list can shift O(n) references, so insort has linear overall work in the worst case. Repeated insertion is not an O(n log n) substitute for one bulk sort.

Common Mistakes

• Keep the sequence sorted before searching it.
• Separate binary search cost from list shifting cost.

Connected lessons

Python binary search: use a half-open interval and require sorted input, Python sorting: stable keys, independent output and explicit tie rules, Python segment tree: point replacement and half-open range sums.

Follow the service contract

Python longest increasing subsequence: reconstruct a strict sequence from tail candidates.

Follow the ownership and update boundary

Python weighted interval scheduling: reconstruct the accepted nonoverlapping jobs.