[Const-me]

One good thing about binary search is memory access pattern.

The element in the middle of the array is tested every single time. Similarly, the elements at 25% and 75% of the array are tested very often, in 50% searches/each.

Modern computers have very slow memory compared to computation speed, and multi-level caches to compensate. Binary search RAM access pattern, when done many times, is friendly towards these multi-level caches. The elements at positions like 25%, 50%, 75% will stay in L1D cache.

[jonstewart]

It’s true that those places will get cached, but binary search tends to dance around the address space a bit too much with large arrays. That’s one of the advantages of interpolation search—provided the items are uniformly distributed.