News for hackers. Stuff that matters.
Re:Binary Search Reconsidered (2018) by tehjoker on Friday December 25, 2020 @12:32PM (#25537754)
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

Funnily enough, the first example of a standard binary search contains the same overflow error.

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-...

Re:Binary Search Reconsidered (2018) by tehjoker on Friday December 25, 2020 @03:15PM (#25538714)
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.
Re:Binary Search Reconsidered (2018) by utopcell on Friday December 25, 2020 @01:51PM (#25538237)
Conveniently, 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.