Binary search: how it works and why it is easy to get wrong

Binary search is one of the simplest algorithms to describe and, surprisingly, one of the easiest to implement badly. The idea fits in one sentence: in a sorted list, look at the middle element and discard the half in which the value you are looking for cannot be. Yet many implementations written on the fly contain boundary errors that only surface in particular cases. Understanding it thoroughly is an excellent exercise in rigorous reasoning.

The idea

Imagine looking for the number 37 in this sorted list:

3  8  12  19  25  31  37  42  50  61  74

Instead of scanning it from the start, you look at the middle element: 31. Since 37 is larger, if it exists it must be in the right half. You repeat on the right half (37, 42, 50, 61, 74): the middle is 50, too big, so you look left. That leaves 37 and 42: found at the next step.

Each comparison halves the search space. That is why the complexity is O(log n): with a million elements about twenty comparisons are enough, against the million a linear search might need.

The fundamental requirement

Binary search works only on sorted data, according to the same criterion used for comparison. If the list is not sorted, the algorithm reports no error: it simply returns wrong results. Sorting costs O(n log n), so it pays off when you make many searches on the same data, or when the data is naturally sorted already, like an event log in time order.

A correct implementation

def binary_search(items, value):
    left, right = 0, len(items) - 1
    while left <= right:
        mid = (left + right) // 2
        if items[mid] == value:
            return mid
        if items[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Every detail matters:

1. right starts at len(items) - 1, the last valid index;
2. the condition is <=, because when left == right there is still one element to check;
3. after the comparison mid is excluded with + 1 and - 1, otherwise the loop may never end.

The classic mistakes

There is also a historical bug related to computing the midpoint: in languages with fixed-size integers, such as Java or C, the sum left + right can exceed the maximum representable value with very large arrays. The form left + (right - left) / 2 avoids the problem. In Python integers have no size limit, so the issue does not arise, but it is worth knowing.

The practical rule to avoid these errors: choose one convention for the bounds and stick to it. Either both inclusive, as in the example, or left inclusive and right exclusive, but never a mix.

Use the library when you can

Python offers the bisect module, which implements binary search correctly and quickly:

from bisect import bisect_left

def index_of(items, value):
    i = bisect_left(items, value)
    if i < len(items) and items[i] == value:
        return i
    return -1

bisect_left returns the position where the value would be inserted to keep the order. That also makes it useful for inserting elements into a sorted list or counting how many values are below a threshold.

Beyond searching for a value

The strength of binary search is that it applies to any problem where a condition is false up to a certain point and true from then on. Some concrete examples:

• finding the first day an indicator exceeds a threshold in a sorted time series;
• finding a faulty version: this is exactly what git bisect does on the commit history;
• finding an optimal value: for example the minimum buffer size that makes a test pass, trying values that get ever closer;
• searching ranges: assigning a score to a band ("up to 18: fail, up to 24: pass...") by looking up the right threshold in a list of limits.

In all these cases you are not looking for an equal element, but for the boundary point. Thinking of binary search in these terms turns it from a textbook exercise into an everyday tool.

How to test it

A binary search should be tested exactly where it most often goes wrong: empty list, single-element list, value in the first and last position, absent value smaller than all or larger than all, duplicate elements. An effective test compares the results with a simple linear search over many generated lists: if the two methods disagree, there is a bug.

In short

• Binary search halves the search space at every step and has O(log n) complexity.
• It only works on sorted data: otherwise it returns wrong results without warning.
• Typical errors concern the bounds: choose a convention and respect it.
• In Python, use the bisect module instead of rewriting it from scratch.
• It applies to any problem with a boundary point, not just to looking up a value.