Re:Binary Search Reconsidered (2018)
by ComputerGuru on Friday December 25, 2020 @02:09PM
(#25538326)
The problem with eytzinger representation is that it is infinitely less useful, and really can only be used as write-once read-many lookup or cache but not as primary storage that is also a cache because it is no longer contiguous.
eg Etyzinger is awesome, but in most real world usage something like this is far more practical and ultimately performant: Faster Lookups, Insertions, and In-Order Traversal Than a Red-Black or AVL Tree [0].
[0]: https://neosmart.net/blog/2019/sorted-list-vs-binary-search-...
You're right about that, but I recently ran into a situation where I had to process about a TB of data repeatedly in that configuration. As a serialized file format, Eytzinger rocked. The IO cost probably dominated, but there was no reason not to use it.
https://algorithmica.org/en/eytzinger
Funnily enough, the first example of a standard binary search contains the same overflow error.