Binary search

Binary search finds a value in a sorted array by repeatedly halving the range that could still contain it. Each comparison discards half the remaining elements, so a search over $n$ items finishes in about $\log_2 n$ steps. That logarithmic cost is why it is one of the most reused primitives in all of computing.

The deeper idea is that binary search works over any monotonic predicate, not just a literal array. If a yes/no condition is false then true as some threshold is crossed, you can binary search for that boundary, which turns many optimization problems into a handful of feasibility checks.

The loop invariant and why it is correct

Maintain two bounds $lo$ and $hi$ with the invariant: if the target is present, it lies in $[lo, hi]$. Each step inspects the middle element and either finds the target or discards the half that cannot contain it, which preserves the invariant while strictly shrinking the range. When $lo > hi$ the range is empty, so the target is absent. Correctness follows directly from the invariant, and termination from the range shrinking every iteration.

The overflow pitfall

Computing the midpoint as $(lo + hi)/2$ can overflow in fixed-width integer languages when $lo+hi$ exceeds the maximum int, a bug that lurked in the standard libraries for years (Bloch 2006). The fix is $lo + (hi - lo)/2$, which never overflows. Python's integers are unbounded so the bug cannot bite here, but it is exactly the kind of detail worth being able to explain.

Binary search on the answer

When a feasibility check $p(x)$ is monotonic, binary search the smallest $x$ with $p(x)$ true. Classic uses are finding an integer square root, the minimum ship capacity to deliver in $D$ days, or the smallest feasible allocation. The why is leverage: instead of trying every candidate, you do $O(\log(\text{range}))$ checks, each often cheap, to pin the boundary.

Boundary variants

Real code usually wants not just membership but the first index whose value is $\ge$ a target (lower bound) or $>$ it (upper bound). These differ only in the comparison and how the bounds update, and getting the off-by-one right is the whole game; most languages ship them (Python's bisect_left and bisect_right).

In Python the bisect module ships both. bisect_left returns the lower bound, the first index where the value could be inserted to keep the list sorted (the first element not less than the target), and bisect_right returns the upper bound (the first element strictly greater). Their difference is the number of occurrences of a value, and insort inserts while preserving order.

import bisect

a = [1, 2, 4, 4, 4, 7, 9]
print(bisect.bisect_left(a, 4))    # 2   lower bound: first index where a[i] >= 4
print(bisect.bisect_right(a, 4))   # 5   upper bound: first index where a[i] > 4
print(bisect.bisect_right(a, 4) - bisect.bisect_left(a, 4))   # 3   count of 4s
print(bisect.bisect_left(a, 5))    # 5   5 would sit between 4 and 7

bisect.insort(a, 5)                # a becomes [1, 2, 4, 4, 4, 5, 7, 9]

# the same lower bound written by hand (the half-open [lo, hi) form)
def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

Step by step

1. Keep a low and high bound on where the target can be.
2. Look at the middle element.
3. If it matches, return its index.
4. If it is too small, discard the left half; if too big, discard the right half.
5. Stop when the bounds cross.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2     # overflow-safe midpoint
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Complexity (time and space)

$O(\log n)$ time, because the range halves each step, so it takes $\lceil \log_2 n \rceil$ iterations, and $O(1)$ space. The precondition is a sorted array; if you must sort first that is an additional $O(n \log n)$, so binary search pays off when you search many times after sorting once.

Worked example

Finding a present value returns its index; a missing value returns $-1$:

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11], 8))   # -1

Follow-up questions

• Why is it O(log n)? Each step discards half the candidates, so the number of steps is how many times $n$ can be halved, which is $\log_2 n$.
• What is the overflow bug and its fix? $(lo+hi)/2$ can overflow a fixed-width int; use $lo+(hi-lo)/2$.
• What is binary search on the answer? Searching the boundary of a monotonic predicate, turning optimization into $O(\log(\text{range}))$ feasibility checks.
• Lower bound vs upper bound? Lower bound is the first index with value $\ge$ target; upper bound is the first with value strictly greater.
• What precondition does it require? The array must be sorted on the key being searched.

References

1. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).
2. Bloch, Nearly All Binary Searches and Mergesorts are Broken (Google Research, 2006).
3. Sedgewick & Wayne, Algorithms (4th ed.).