News for hackers. Stuff that matters.

A comment on Binary Search: A new implementation that is up to 25% faster. Parent comment

Re:Binary Search: A new implementation that is up to 25% faster by ghj on Monday July 20, 2020 @06:45AM (#23896529)
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

[ Parent | on HN ]
Re:Binary Search: A new implementation that is up to 25% faster by fluffything on Tuesday July 21, 2020 @05:56AM (#23905624)
Yes, its essentially a heap. These just happens to be cache oblivious for performing binary searches.
[ Parent | on HN ]