bisect and Sorted-List Maintenance

### Insertion point, not position Both functions answer the same question — *where would x go?* — and neither reports whether x is present. The result is always an integer in `0..len(a)`: `0` when x sorts below everything, `len(a)` when it sorts above everything. Nothing raises, and nothing returns a sentinel like -1. The two differ only in how they treat elements that compare **equal** to x, and the documented invariants are the cleanest way to remember which is which. For `i = bisect_left(a, x)`: every element of `a[:i]` is strictly less than x, and every element of `a[i:]` is greater than **or equal to** x. For `i = bisect_right(a, x)`: every element of `a[:i]` is less than **or equal to** x, and every element of `a[i:]` is strictly greater. So `bisect_left` lands on the first element not less than x, and `bisect_right` lands one past the last element not greater than x. If x is absent, the two agree; the split only becomes visible once duplicates exist. ```pycon >>> import bisect >>> a = [10, 20, 20, 20, 30] >>> bisect.bisect_left(a, 20), bisect.bisect_right(a, 20) (1, 4) ``` ### The four idioms that follow **Extract the run.** `a[bisect_left(a, x):bisect_right(a, x)]` is exactly the block of values equal to x. On the list above that is `[20, 20, 20]`. **Count occurrences.** `bisect_right(a, x) - bisect_left(a, x)` is the number of copies, computed in two logarithmic searches rather than a scan. Getting the subtraction backwards yields a negative number, which is a fine self-check. **Test membership.** `i = bisect_left(a, x); found = i != len(a) and a[i] == x`. The length guard matters: when x sorts above everything, `i == len(a)` and indexing would raise `IndexError`. If membership is *all* you need, a `set` is the better structure — bisect earns its keep when you also want order, ranges or neighbours. **Find the last value at or below x.** `bisect_right(a, x) - 1` is the index of the greatest element not exceeding x, the standard "most recent reading at or before this timestamp" lookup. A result of `-1` means there is none, so guard it rather than letting the negative index wrap to the end of the list. ### The insort side of the split `bisect.insort_left` and `bisect.insort_right` place a new item on the corresponding side of any equal-comparing items already present. For plain scalars the choice is invisible — one `20` is indistinguishable from another. It becomes observable the moment the items compare equal but differ in payload: tuples ordered by a leading timestamp, or records searched with a `key=` function that ignores the rest of the object. There, `insort_right` appends after the existing equals and preserves arrival order among ties (FIFO), while `insort_left` puts the newcomer in front of them (LIFO). Say which behaviour you want; the default alias `insort` is `insort_right`. One trap with tuples: if the leading fields tie, comparison falls through to the next field. Should that field be an unorderable payload — a dict, say — the insert raises `TypeError` only on the unlucky duplicate, so the bug shows up in production rather than in the happy-path test. Give the tuple a monotonically increasing tiebreaker before the payload. ### Bounds, and what is not checked Both functions take `lo` and `hi` to restrict the search to `a[lo:hi]` without slicing, which matters because a slice copies the segment and would swamp the logarithmic search. They also assume ascending order and never verify it: handed unsorted input they return a number computed from a false premise, with no exception at all. Finally, these functions call `__lt__` on the elements, so the cost per comparison is the element's own comparison cost. Deeply nested tuples or objects with an expensive `__lt__` turn a cheap logarithmic search into a measurable one; extracting a scalar key is the usual remedy. ### The names in other languages If it helps anchoring: `bisect_left` is the classic lower bound and `bisect_right` the upper bound found in other standard libraries. Interviewers sometimes use those names, and recognising the mapping is worth a sentence. ### Why an insertion point rather than a found index Returning a position that is always valid, present or absent, is what makes the API compose. One call answers membership, the predecessor, the successor, the count of equals and the place to insert, all by arithmetic on the same integer — no exception handling, no sentinel to test for, no second search. Contrast `list.index`, which raises `ValueError` when the value is missing and scans linearly when it is not. The price is that you must decide for yourself what absence means in your case, and that decision is exactly the `a[i] == x` guard people forget.