scandum / binary_search

The most commonly used binary search variant was first published by Hermann Bottenbruch in 1962 and hasn't notably changed since. Below I'll describe several novel variants with improved performance. The most notable variant, the monobound binary search, executes up to 60% faster on 32 bit integers.

A source code implementation in C is available licensed under GPL 3 (a less restrictive license may be negotiated) and is bundled with a bench marking routine. A graph with performance results is included at the bottom of this page. Keep in mind performance will vary depending on hardware and compiler optimizations.

I'll briefly describe each variant below.

Deferred Detection of Equality

By skipping the detection of equality until the binary search has finished (which does not allow for early termination) each loop contains 1 key check, 1 integer check and 2 integer assignments. This is pretty much the standard algorithm that has been used since 1962.

Pointer Optimizations

You can get another 10% performance boost by using pointer operations. I forgo such optimizations in the C implementation to keep things as readable as possible.

Unsigned Integer Optimization

You can get a further performance boost by using unsigned instead of signed integers.

Tailed Binary Search

This binary search variant has the same number of key checks as the standard binary search, except that the calculations are slightly less complicated, giving it a slight performance gain without drawbacks.

Boundless Binary Search

The boundless binary search is significantly faster than the standard binary search since the loop contains 1 key check 1 integer check and (on average) 1.5 integer assignments. The performance gain will vary depending on various factors, but should be around 40-60% when comparing 32 bit integers. It performs more key checks.

Inbound Binary search

The inbound binary search has less complex computations than the boundless binary search. Performance is similar.

Monobound Binary search

The monobound binary search is similar to the boundless binary search but uses an extra variable to simplify calculations. It's slightly faster than the boundless binary search.

Monobound Quaternary Binary Search

The monobound quaternary binary search has more key checks than the boundless binary search but runs faster on large arrays.

Monobound Interpolated Binary Search

When you have an even distribution you can make an educated guess as to the location of the index. Due to the expense of the initial check and exponential search, the interpolated binary search is unlikely to outperform other binary searches on arrays with less than 1000 elements. When the distribution is uneven performance will drop, but not significantly.

Benchmark graph

The graph below shows the execution speed on arrays with 10, 100, 1000, 10000, 100000, and 1000000 elements on an Intel i3 quad-core processor. The Y axis lists the execution time in microseconds.

Benchmark tables

The following benchmark was on WSL gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). The source code was compiled using gcc -O3 binary-search.c

Even distribution with 10 32 bit integers

Even distribution with 100 32 bit integers

Even distribution with 1000 32 bit integers

Even distribution with 10000 32 bit integers

Even distribution with 100000 32 bit integers

Even distribution with 1000000 32 bit integers