The Mathematics Behind Search Algorithms

Binary search is one of the simplest algorithms in computer science. Look at the middle of a sorted list; if your target is smaller, search the left half, otherwise the right half. Repeat.

Yet in his book Programming Pearls, Jon Bentley reported that when he assigned it to professional programmers in courses, about 90% of them wrote versions with bugs. And in 2006, Google engineer Joshua Bloch revealed that the binary search in Java's standard library, which he had written, contained a bug that had gone unnoticed for about nine years.

Searching looks easy. The mathematics behind doing it correctly and quickly is where things get interesting.

Sorting First Makes Search Exponentially Faster

Searching an unsorted list means checking items one by one. For a billion items, that could be a billion comparisons.

If the list is sorted, binary search needs at most about 30. Sorting costs time up front, but it changes search from growing linearly to growing logarithmically. For repeated searches, organizing the data is everything.

Linear Search: O(n)

Check each item until you find the target. On average, for an item that's present, you'll look at about half the list. In the worst case, all of it.

Expected comparisons (target present, random position) = (n + 1) / 2

It's the right choice only for small or unsorted data you'll search once.

Binary Search: O(log n)

Each comparison halves the remaining range. After k comparisons, n/2ᵏ items remain. The search ends when that reaches 1:

n / 2ᵏ = 1   →   k = log₂ n

Adding a thousand times more data adds only about 10 more steps. Explore powers of two in the base-2 logarithm table.

An Insider Reference: The Binary Search Bug

Donald Knuth noted in The Art of Computer Programming that although the idea of binary search was published in 1946, the first version that handled every case correctly didn't appear until 1962.

Joshua Bloch's 2006 blog post, "Nearly All Binary Searches and Mergesorts are Broken," explained the Java bug. The line was:

int mid = (low + high) / 2;

It looks mathematically perfect. But if low + high exceeds 2,147,483,647, the largest 32-bit signed integer, the sum overflows and becomes negative. That only happens with arrays of over a billion elements, which were rare when the code was written. The fix:

int mid = low + (high - low) / 2;

It's the same value mathematically, but it never exceeds high. The lesson: mathematical correctness and machine arithmetic aren't the same thing. See why in How Computers Represent Numbers.

Hashing: O(1) on Average

Hash tables skip comparisons entirely. A hash function turns the key into an array index:

index = hash(key) mod table_size

With a good hash function and a table that isn't too full, a lookup takes constant time on average, no matter how much data you store. The price: no ordering (you can't ask for "the next largest key") and occasional collisions to resolve. See Hash Functions: The Mathematics Behind Modern Software.

B-Trees: Search on Disk

Binary search assumes jumping anywhere in the data is cheap. On disks, each jump can be slow. In 1972, Rudolf Bayer and Edward McCreight, working at Boeing Scientific Research Labs, published the B-tree.

Instead of 2 branches per node, a B-tree node can have hundreds or thousands. With a branching factor of about 1,000:

Level 1: 1,000 entries
Level 2: 1,000,000 entries
Level 3: 1,000,000,000 entries

A billion records need only about 3 or 4 node reads. That's log base 1,000 instead of log base 2. Almost every relational database and file system uses B-trees or their relatives today.

Searching Text: Inverted Indexes

Search engines don't scan every document. They build an inverted index, a map from each word to the list of documents containing it, just like the index at the back of a book.

To rank results, they score how well each document matches. A classic formula is BM25, developed by Stephen Robertson and colleagues in the 1990s, which refines TF-IDF:

• Term frequency: more occurrences of a word in a document suggest relevance, with diminishing returns
• Inverse document frequency: rare words matter more: IDF ≈ log(N / documents containing the word)
• Length normalization: long documents shouldn't win just by being long

The logarithm keeps common words from dominating. Try it with the logarithm calculator.

Searching Graphs

Some searches explore connections rather than lists:

• Breadth-first search finds the fewest hops between two people in a social network
• Depth-first search explores mazes and dependency trees
• Dijkstra's algorithm and A* find shortest weighted routes, as in map navigation

Each runs in time proportional to the number of nodes and edges, with a logarithmic factor when a priority queue is used. See The Math Behind Google Maps.

Two Concepts Worth Knowing

Logarithm

A logarithm counts how many times you divide by a base to reach 1. Binary search is log₂, B-trees are log₁₀₀₀, and both grow extraordinarily slowly.

Invariant

A search algorithm's invariant is a statement kept true at every step, such as "if the target exists, it's between low and high." Stating it clearly is the best defense against off-by-one bugs.

Quick Answer: What Math Is Behind Search Algorithms?

Linear search takes time proportional to n. Binary search halves a sorted range each step, taking about log₂ n comparisons, so a billion items need about 30. Hash tables use hash functions and modular arithmetic for constant average time, B-trees use high branching factors to minimize disk reads, and text search ranks results with logarithmic scoring like TF-IDF and BM25.

Try Them Yourself

• Base-2 Logarithm Table: comparisons needed for binary search
• Logarithm Calculator: log base 1,000 for B-trees
• Number Theory Formulas: modular arithmetic in hashing
• List of Prime Numbers: prime table sizes for hash tables
• Why Every Programmer Should Understand Big-O Notation: comparing growth rates
• The Math Behind Google Search: ranking on the scale of the web

Ask a friend to think of a number from 1 to 1,000,000. Use binary search with yes/no questions. You'll never need more than 20 guesses.