Hacker News Reader

Not really.

On a GPU for example, if you have an array with 100.000 elements and want to find the index of one value, you are probably best of by using 100.000 threads to find that value.

So that's 100.000-ary search.

On a CPU, using an Eytzinger layout will probably also give you better performance than any of the N-ary approaches.

View on HN

I've never heard of the eytzinger layout but it seems like it's just a static binary tree on a array (children are at 2i and 2i+1), commonly used for heaps and segment trees.

Very readable blog post on how it helps with binary search: https://algorithmica.org/en/eytzinger

With follow up post on N-ary approaches: https://algorithmica.org/en/b-tree

Yes, its essentially a heap. These just happens to be cache oblivious for performing binary searches.

Reply on news.ycombinator.com