Wikipedia quite authoritatively states that "Binary search is faster than linear search except for small arrays", which has been a well accepted truth for many years, but this is no longer the case.

The traditional binary search which was developed more than 50 years ago, and which is used by virtually every software application in existence, is slower than a linear search for arrays under 64-80 elements on most benchmarks. The reason for this can be attributed to the use of computations that are difficult to optimize by a compiler.

The boundless binary search, which I wrote back in 2014, improved the situation, and it was slower than a linear search up until 32-48 elements.

Next I wrote yet another variant, the monobound binary search, which is slower up until 8-16 elements. Almost there, but not quite.

While messing around the other day I came up with the tripletapped binary search variant (after writing the doubletapped variant) which is just as fast as linear under 4 elements, and becomes faster above.

The tripletapped binary search implementation in C and a benchmark are available at https://github.com/scandum/binary_search, and the github repository also contains some other interesting binary search variants.

Using this benchmark I created the following graph.

The Y axis is the cpu time, the x axis is the array size.

So the next time someone asks "At which N does a binary search become faster than a linear search" the answer is 4.

Naming

As for the names doubletapped and tripletapped, once a traditional binary search narrows down the search range to 2 elements it takes exactly 2.0 more key checks to complete the search. The doubletapped binary search creates a special case for the final 2 elements and allows for early termination, resulting in an average case of 1.5 key checks.

The monobound binary search takes exactly 3 key checks to finish once it narrows down the search range to 3 elements. By using a special case for the final 3 elements it reduces an average of 3.0 key checks to 2.0.

Subsequently, the tripletapped search has the same number of key checks as a linear search for the first 3 elements, while the worst case number of key checks for 4 elements remains at 3.0 for the trippletapped search, and rises to 4.0 for the linear search.

While the benchmark shows the tripletapped and standard search to be equally matched at 4 elements, this is when comparing 32 bit integers. Change the payload to something heavier and the tripletapped search wins with ease.