Beautiful branchless binary search

A cool related algorithm is https://algorithmica.org/en/eytzinger

In addition to being branchless, it also has better cache properties than a standard binary search tree.

If you're doing a binary search in an array, you start in the middle, and then jump all the way to the midway point of one half, and so on. As a result, there's a lot of distance between each read that you do in the array. Thus, each read is putting extra strain on the cache (or the reads won't be cached).

The CPU cache performs much better if the values you want to read are close to each other. Enter the Eytzinger Binary Search. The idea is that, if you're always going to be accessing the root of the tree, and then one of its two children--you should just put those children physically close to the root, so they'll all be on the same cache line!

Isn't that like storing a heap inside an array, with indices and values like this:

    0: top of heap,
    1: left of top,
    2: right of top,
    3: left of left of top
    ...

?

It is, but so is storing a sorted array.

It's still misleading to call this a binary search when that is commonly understood as an algorithm operating on a sorted range which is not just an arbitrary datastructure but something that already exists in many situations. If you just need fast lower_bound lookup for a set that you control and which has no other uses then sure this is nice, but more commonly you only care if an element is in the set and in that case if you can control the data structure then there are many more options.