Binary search into a sorted array is slow. Intro algorithms classes might count operations, and you discover that about log_2(n) operations are needed, which is optimal in a certain sense.

But those operations are horrible operations. Until you are log_2(cache line size / element size) steps from the leaves, you are hitting a different cache line each time, and you’re doing a branch such that the next cache line you want depends on the branch result.

So this is like log_2(n)-3 serial (cache miss, compare, branch, compute address operations). (Assume 8-byte entries — it’s much worse with bigger entries.) This not even close to optimal.

You will find that, for reasonably large data sets (maybe a few hundred elements or more?), any cache-optimized searchable data structure will beat binary search by a large factor. And for small arrays (or the last stage of an optimized large structure), you want a vectorized linear search.

Binary search is mostly nice because sorted arrays are elegant and binary search can be implemented in very little code. And it’s easy to explain and analyze.