From algorithm to code

An algorithm is an idea: "look at the middle, throw away the half that can't contain the target, repeat." A program is thousands of precise decisions that the idea leaves open. Where does the range start and end? What if the list is empty? What type holds an index? What does "not found" return? Most bugs live in these decisions, not in the idea.

This chapter, the last of the algorithms level, takes one algorithm, binary search, described in the searching and sorting chapter, all the way from an idea to machine code running on a real CPU. Along the way it shows the tools that make the translation reliable: a precise pseudocode, an explicit invariant, tests that try every edge case, and a look at what the compiler actually produced.

From idea to pseudocode

The first step is to write the algorithm precisely enough that every decision is made, but without committing to a language. A good pseudocode for binary search makes the range explicit:

search(a[0..n), x):            -- a is sorted; find x, or report that it's absent
    lo ← 0, hi ← n              -- the part of a still to be searched is a[lo..hi)
    while lo < hi:
        mid ← a point with lo ≤ mid < hi, near the middle
        if a[mid] < x:  lo ← mid + 1     -- x can only be to the right of mid
        if a[mid] > x:  hi ← mid         -- x can only be to the left of mid
        if a[mid] = x:  return mid
    return "absent"

The notation a[lo..hi) is a half-open interval: it includes lo and excludes hi. This is a choice, and it's the choice that makes everything else simple. The whole array is a[0..n); the empty range is lo = hi; the number of elements left is hi − lo. Mixing half-open and closed ranges in the same loop is the most common source of binary search bugs.

Pseudocode to C

Translating to C forces the remaining decisions:

• "absent" has to be a value. Returning −1 works because valid indexes are never negative.
• Indexes need a type. int is fine for arrays of fewer than 2³¹ elements; for anything bigger, C programmers use size_t, and the type turns out to matter, as we'll see.
• "near the middle" needs a formula. (lo + hi) / 2 looks obvious. It has a bug.

int bsearch_int(const int *a, int n, int x) {
    int lo = 0, hi = n;              /* invariant: if x is in a, it is in a[lo..hi) */
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < x) lo = mid + 1;
        else if (a[mid] > x) hi = mid;
        else return mid;
    }
    return -1;
}

Choosing the data structure

Binary search only works on data kept sorted in an array: it needs to jump to any position in O(1), which a linked list can't do. So the algorithm dictates the structure, and the structure has its own costs: inserting into a sorted array means shifting everything after the new element, O(n).

That's why the choice depends on what else the program does with the data:

Choosing the structure is part of choosing the algorithm. The best search is useless if keeping the data sorted costs more than it saves.

Invariants: why the loop is right

How do we know the loop is correct? Not by trying a few examples, but by stating what stays true at every step (the loop invariant) and checking three things:

1. It's true at the start. Before the loop, lo = 0 and hi = n: the range is the whole array, so if x is in a, it's in a[lo..hi). True.
2. Each step keeps it true. If a[mid] < x, then because the array is sorted, every element up to and including mid is less than x, so x can only be in a[mid+1..hi), hence lo = mid + 1. If a[mid] > x, then x can only be in a[lo..mid), hence hi = mid, not mid − 1, because hi is excluded.
3. When the loop ends, it gives the answer. The loop ends with lo = hi: the range is empty, so by the invariant x isn't in a, and returning −1 is right.

We also need the loop to terminate: hi − lo is a whole number that decreases strictly at every step (mid lies in [lo, hi), so both lo = mid + 1 and hi = mid shrink the range), and it can't go below zero. The invariant tells us the program is right if it stops; the shrinking range tells us it stops.

Each line of the code follows from the invariant. That's the real use of invariants: not as documentation written afterwards, but as the tool that tells you, while writing, whether it's mid or mid − 1, < or <=.

Testing the edges

Reasoning catches most bugs; tests catch the rest, and the bugs of binary search hide at the edges: an empty array, a one-element array, a target before the first element, after the last, between two elements, equal to the first or the last. A small search function has a small input space, so we can test all of it up to some size, and compare against a version too simple to be wrong: here, linear search.

The demo below tries every array size from 0 to 16, filled with 1, 3, 5, …, and every target from 0 to 2n + 1, so that every element and every gap is searched for. Each square is one test, compared against linear search:

The correct version passes all 306 tests, with 964 probes in all. Now break it on purpose, as a real programmer would by accident:

• hi = mid - 1 mixes up closed and half-open ranges: 56 failures out of 306. The search skips elements that sit right next to a discarded midpoint. Click a red square to see which one it jumped over.
• lo <= hi lets the loop run once more when the range is empty. When lo = hi and a[mid] > x, the assignment hi = mid changes nothing, and the loop spins forever: 136 of the tests never finish. And every search for a target larger than the last element ends up reading a[n], one element past the end of the array.

Exhaustive testing of small cases is one of the most effective techniques there is: it's cheap, it finds exactly the edge cases people forget, and bugs in algorithms like this one almost always show up on small inputs.

The overflow nobody tested

Here is what the two midpoint formulas give with 32-bit ints when lo is 1.5 billion and hi is 2 billion:

(lo + hi) / 2      = -397483648
lo + (hi - lo) / 2 = 1750000000

The sum lo + hi, 3.5 billion, doesn't fit in a 32-bit int, whose maximum is 2,147,483,647. It wraps around to a negative number (the data types chapter explains why), and the "midpoint" becomes −397,483,648. The safe formula never computes anything larger than hi.

This is the bug that sat in Java's Arrays.binarySearch for about nine years until Joshua Bloch reported it in 2006, after it hit a real program. It wasn't caught because testing it requires an array of more than a billion elements, and nobody tests with those. We can. A C program can reserve 8 GB of address space for 2 billion ints with mmap; the pages are never touched except the thirty or so that binary search reads, so they cost almost no real memory. Searching it for a value larger than every element pushes lo toward the end, and the sum overflows. On this Mac:

Neither "working" result is a reprieve. The unoptimized build reads memory that doesn't belong to the array, and whether that crashes depends on where address-space randomization placed things on that run. As for the optimized build: in C, signed overflow is undefined behavior, so the compiler may assume it never happens, and clang, reasoning that lo + hi is therefore never negative, computed the midpoint with an unsigned shift, which happens to give the right answer here. A different compiler, version or surrounding code can make a different choice. The undefined behavior sanitizer (-fsanitize=undefined) is the tool that reports the bug regardless. One more reason to run tests with sanitizers turned on.

What the compiler makes of it

Here is the correct version compiled by clang with -O2 for x86-64:

bsearch_int:
    test    esi, esi              ; n <= 0? then not found
    jle     .notfound
    xor     ecx, ecx              ; lo = 0
    jmp     .loop
.right:
    inc     eax                   ; mid + 1
    mov     ecx, eax              ; lo = mid + 1
    mov     eax, esi              ; hi unchanged
.left:
    mov     esi, eax              ; hi = mid (or unchanged)
    cmp     ecx, eax
    jge     .notfound             ; while (lo < hi)
.loop:
    mov     eax, esi
    sub     eax, ecx              ; hi - lo
    shr     eax                   ; / 2, as an unsigned shift
    add     eax, ecx              ; + lo = mid
    cmp     dword ptr [rdi + 4*rax], edx    ; a[mid] vs x
    jl      .right
    jg      .left
    ret                           ; equal: return mid
.notfound:
    mov     eax, -1
    ret

(Comments added; labels renamed.) The division by 2 became a single shr. For a signed int, / 2 normally needs extra instructions to round toward zero for negative numbers, but the compiler proved that hi − lo is never negative inside the loop, the same fact as our invariant. The comparison a[mid] < x is one cmp with a scaled-index memory operand, as in the addressing modes chapter, and the three-way if is two conditional jumps on the same flags. For 64-bit ARM, clang computes the whole midpoint in two instructions, the second one shifting and adding at once:

    sub     w8, w1, w9            // hi - lo
    add     w8, w9, w8, lsr #1    // lo + (hi - lo) / 2
    ldr     w10, [x0, w8, uxtw #2]        // a[mid]

How it runs

On the real machine, the algorithm's big-O shows up almost exactly. Searching a sorted array of one million ints for 2,000 random values (half of them absent):

About 2,000 times faster, as the complexity chapter predicts: 20 probes instead of hundreds of thousands of comparisons. But 20 probes taking about 100 ns means roughly 5 ns per probe, far more than the handful of instructions each one executes. The probes jump around a 4 MB array, so the first few usually miss in the caches, and the direction of each step is random, so the conditional jumps are mispredicted about half the time. Fast implementations replace the jumps with conditional moves and lay the array out in a cache-friendly order: the same algorithm, adapted to the machine below it.

Handing off to the programming languages level

That's the path every program takes: an algorithm, made precise as pseudocode and invariants, translated into a language whose details (integer types, overflow, undefined behavior) can break a correct idea, then compiled into instructions whose speed depends on caches and branch predictors.

The next level down is the programming language itself. High-level languages are usually described as translated by compilers, occasionally interpreted, and Java as compiled to bytecode that is then interpreted. That has long been incomplete: the Java virtual machine compiles frequently run bytecode to machine code while the program runs. The compiled, interpreted and JIT-compiled languages chapter starts there, with the same loop run three ways.

Takeaways

• Most bugs live in the decisions an algorithm leaves open: range boundaries, empty inputs, types, return values.
• Write pseudocode with explicit ranges; use half-open intervals [lo, hi) consistently.
• The loop invariant, "if x is in a, it's in a[lo..hi)", dictates each line; a strictly shrinking hi − lo proves termination.
• Test exhaustively on small inputs against a trivially correct version: 306 cases caught hi = mid − 1 (56 failures) and lo <= hi (never terminates).
• (lo + hi) / 2 overflows past 2³¹; on a real 2-billion-element array it crashed or read outside the array at -O0, worked by luck at -O2, and was reported by -fsanitize=undefined. Use lo + (hi − lo) / 2.
• The compiler turns / 2 into one shift because it can prove the value is non-negative; on the real CPU, binary search was 2,000 times faster than linear search, and its remaining cost is cache misses and branch mispredictions.