How Binary Search Works: Halving Your Way to Any Value

Binary search is one of the first algorithms most programmers learn, and it is one of the most useful. Given a sorted list, it tells you whether a value is present and where it sits, by checking the middle element and discarding half of the remaining candidates. A sorted list of one million numbers needs at most about twenty comparisons with this method, while a simple scan may need one million.

This article explains the idea step by step, shows a working implementation, and covers the edge cases that cause most real bugs. It assumes only that you can read a loop and compare two numbers.

The core idea

Suppose someone picks a number between 1 and 100 and asks you to guess it. Each answer you receive is "higher", "lower" or "correct". A careless strategy guesses 1, then 2, then 3, and so on. In the worst case that takes 100 guesses. A better strategy guesses 50 first. If the answer is "higher", the number must be between 51 and 100, so half of the candidates are gone at once.

Binary search applies the same strategy to a sorted array. It keeps two indexes, called low and high, that mark the part of the array that could still contain the target. At each step it looks at the middle index, compares the value stored there with the target, and then moves either low or high so that the range shrinks.

The word "sorted" matters. The method depends on the fact that every value to the left of the middle is smaller than the middle value, and every value to the right is larger. Without that order, a single comparison tells you nothing about the rest of the array.

Step by step on a small example

Take the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] and search for 23.

Start with low = 0 and high = 9. The middle index is 4, which holds 16. Since 23 is greater than 16, the target can only be in the right half, so low becomes 5.

Now low = 5 and high = 9. The middle index is 7, which holds 56. Since 23 is smaller than 56, the target can only be in the left part, so high becomes 6.

Now low = 5 and high = 6. The middle index is 5, which holds 23. That is the target, so the search returns index 5.

Three comparisons found a value in a list of ten. A linear scan needs six comparisons to reach the same value.

Why the number of steps is logarithmic

Each comparison cuts the candidate range roughly in half. If the range starts with n elements, then after k comparisons at most about n divided by 2 to the power k elements remain. The search ends when a single candidate remains, so the number of comparisons is about the base-2 logarithm of n.

The worst-case count is therefore about log2(n), rounded up. The table below compares that growth with a linear scan.

List size (n)	Linear scan, worst case	Binary search, worst case
10	10	4
1,000	1,000	10
1,000,000	1,000,000	20
1,000,000,000	1,000,000,000	30

Doubling the list adds only one extra comparison, which is why the method scales so well as data grows.

A correct implementation

Most bugs in this algorithm come from loop boundaries and from the way the middle index is computed. The Python version below uses inclusive bounds and returns -1 when the target is missing.

def binary_search(items, target):
    # Inclusive bounds: both low and high are valid candidate indexes.
    low, high = 0, len(items) - 1
    while low <= high:
        # Written this way to avoid overflow in languages with fixed-width integers.
        mid = low + (high - low) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1   # the target can only be to the right of mid
        else:
            high = mid - 1  # the target can only be to the left of mid
    return -1               # the range became empty, so the value is absent

The loop condition uses less-than-or-equal because a range with one candidate is still a valid range. A strict comparison there is a classic off-by-one error that makes the function miss the last element.

The midpoint is computed as low plus half of the gap instead of (low + high) divided by 2. Python integers never overflow, but in C, C++ and Java, adding two large indexes can exceed the maximum value of a 32-bit integer. The safer form avoids that case entirely.

Edge cases that cause real bugs

Several situations deserve explicit tests.

An empty list must return -1 immediately. The code above handles it, because high starts at -1 and the loop never runs.

A target smaller than the first element or larger than the last element must also return -1 without an index error. The bound updates keep low and high inside the array, so this case works without extra checks.

Duplicate values are a subtle point. The function above returns some matching index, but not necessarily the first or the last one. If your program needs the first occurrence, you must keep searching to the left after a match, or use a variant that narrows toward the boundary.

Finally, the list must be sorted by the same ordering that the comparisons use. Sorting by one key and searching by another produces wrong answers that look like random misses.

Binary search beyond arrays

The same idea works on any monotonic condition, not only on lists of numbers. Many standard libraries expose it under names such as lower bound or upper bound. C++ provides std::lower_bound and Python provides the bisect module for sorted sequences.

A broader pattern is to search over an answer space. If you can write a test that is false for small values and true for large values, binary search finds the boundary in logarithmic steps. This technique is common when the question is "what is the smallest value that works?" rather than "where is this item stored?"

Common mistakes to avoid

Developers new to the method often make the same few errors. They forget to update low or high after a comparison, which causes an infinite loop. They mix inclusive and exclusive bounds in the same function. They search an unsorted list and blame the algorithm. They also assume the function returns the first match when the code does not guarantee it.

A useful habit is to test with lists of length zero, one and two, plus targets at both ends and just outside the range. Those tests catch most mistakes within minutes.

Key takeaways

Binary search finds a value in a sorted collection by repeatedly checking the middle element and discarding the half that cannot contain the target. Its worst-case cost grows with the base-2 logarithm of the list size, so a list of a billion items needs about thirty comparisons.

The method is correct only when the data is sorted under the same order used by the comparisons. Careful loop bounds, safe midpoint arithmetic and explicit tests for empty and duplicate cases are what make an implementation reliable in practice.