Binary search

Binary search finds a target in a sorted sequence by checking the middle and discarding the half that cannot contain it. With direct access to the middle item, each comparison halves the remaining range, so target lookup takes O(log n) comparisons. Python’s bisect extends that idea to insertion points, where duplicates and the cost of moving elements become the next questions.

Find a target by halving the range#

Take the sorted array [2, 5, 8, 12, 16, 23, 38] and find 16. The middle value is 12 at index 3, so discard indices 0–3. The middle of the remaining range is 23 at index 5, so discard it and everything after it. Index 4 holds 16: found. For target 15, the final comparison with 16 instead empties the range, so the function returns -1.

def binary_search(values, target):
    low, high = 0, len(values)  # search [low, high)
    while low < high:
        mid = low + (high - low) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid
    return -1  # no matching value

The code keeps a half-open candidate range [low, high). When the middle is too small, the next candidate starts at mid + 1; when it is too large, the upper boundary becomes mid. Each step removes at least half the candidates, giving O(log n) comparisons and O(1) extra space. That bound assumes the data is already sorted and midpoint access is O(1), as with an array. Sorting first has its own cost, and inserting into a Python list after the search can still take O(n).

It finds a position, not a value#

Target lookup asks whether an equal value exists. A lower-bound search asks a related question: where would this value first fit without breaking the sorted order? It still halves a candidate range, but it continues until it has an insertion position even if no equal element is present. A balanced search tree makes repeated narrowing 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. They differ whenever the searched value is present, even if it appears only once. They return the same position only when no equal value is present. 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 useful 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 just to run one search costs more asymptotically than scanning it. A sorted linked list can stop a linear search early, but it cannot provide the O(1) midpoint access needed for this O(log n) array search. 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.