Discarding half the candidate interval
For an array ordered by the same comparison rule, a midpoint comparison identifies which half can still contain the target. Search maintains that candidate interval until it finds a match or narrows the range enough to establish absence.
Correctness depends on ordering and interval invariants, not simply the ability to jump to the middle. Boundary updates must make progress, including for an empty array, one element, and queries outside both ends.
Equality and insertion boundaries differ
With duplicates, an arbitrary equal item, the first equal position, and the position after equal items are different results. Python bisect_left returns an insertion point before existing equals, while bisect_right returns one after them.
These bisect interfaces partition through less-than comparisons rather than calling equality to prove a match. Exact lookup still checks that the returned position is in range and contains an equal value under the required contract. An insertion point alone is not a successful search.
References: [2]
Comparisons and updates have separate costs
For an indexed array, repeated halving needs O(log n) comparisons. Long-key comparisons or a representation without direct midpoint access contribute additional work beyond the comparison count.
Finding an insertion position does not make insertion logarithmic. Python list insort still shifts elements and is O(n). Concurrent modification can invalidate ordering and interval assumptions; the bisect documentation does not guarantee safe concurrent use on the same sequence.