Binary search

Binary search is taught as a way to find a value quickly, and that description quietly hides the thing that makes it useful. What the algorithm computes is a position — the place in a sorted sequence where a value belongs. Whether something is already sitting at that place is a separate question, and keeping the two apart explains most of the design decisions in any library that ships it.

It finds a position, not a value#

The mechanism is a repeated halving. Look at the middle of the range; if the target sorts before it, the answer lies in the left half, and if after, the right. Either way half the remaining candidates are eliminated by a single comparison, and the range keeps halving until one position is left. Twenty comparisons cover a million elements, thirty cover a billion, and the growth is so slow that the size of the collection almost stops being a consideration. A balanced search tree makes the same halving structural rather than arithmetic, which is why walking one in order comes out sorted.

Python’s bisect module makes the framing explicit rather than leaving it as an implementation detail. Its documentation notes that, unlike other tools that search for a specific value, these functions are designed to locate an insertion point — and draws the consequence that surprises people: the functions never call eq to determine whether a value has been found, only lt. The search is conducted entirely in terms of ordering. Equality never enters into it, so an object whose ordering and equality disagree will be placed by the first and not consulted about the second.

Left and right are a decision about duplicates#

Once the answer is a position, duplicates stop being an edge case and become a question the caller has to answer. If a sorted list already holds three copies of a value, there are four positions where a fourth could go, and two of them are interesting: immediately before the existing run, or immediately after it.

That is why the module ships both. bisect_left returns an insertion point before any existing entries equal to the value; bisect_right returns one after them. On a list with no duplicates they are identical, which is precisely the trap — code written and tested against distinct values behaves the same either way, and starts differing on the day real data arrives with repeats in it. Choosing between them is choosing whether a new equal element is treated as arriving before or after the ones already there, and that is a decision about your data, not about the algorithm.

The search is rarely the cost#

The logarithmic search is so cheap that it usually stops being what the operation costs, and Python’s documentation puts the point bluntly where it matters most — for insertion, the O(log n) search is dominated by the slow O(n) insertion step. Finding where an element belongs in a sorted array takes a handful of comparisons. Putting it there means shifting everything after it along by one, and that is proportional to the size of the array. Maintaining a sorted list by repeated insertion is therefore a linear operation wearing a logarithmic label.

There is a second cost that is easy to miss, and it decides whether binary search is available at all: the sequence has to be sorted, and it has to support jumping straight to the middle. Both are real constraints. Sorting an unsorted collection to run one search is worse than scanning it, and a structure with no cheap way to reach its midpoint cannot be searched this way at all — which is why a linked list gets no benefit from being in order. When the question is simply whether a specific value is present, the documentation offers the plainer advice: for locating specific values, dictionaries are more performant.