4 ms·
I wonder if it's easier to write an eytzinger binary search (which is also cache-aware and therefore faster): https://algorithmica.org/en/eytzinger https://alg
by tehjoker 6y ago
I wonder if it's easier to write an eytzinger binary search (which is also cache-aware and therefore faster):
https://algorithmica.org/en/eytzinger https://algorithmica.org/en/eytzinger
Funnily enough, the first example of a standard binary search contains the same overflow error.
- utopcell 6y agoConveniently, we are not shown the type of n or its valid input range: if it is a int16_t or we know it to be upper bounded by 1<<30, that's proper vanilla binary search.
- ComputerGuru 6y agoThe 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-tree/ https://neosmart.net/blog/2019/sorted-list-vs-binary-search-...
- tehjoker 6y agoYou'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.