An interesting data structure with search time O(sqrt n)

[Andrei Alexandrescu via Digitalmars-d]

On 12/02/2015 06:26 AM, Timon Gehr wrote:
> The linear search can have way better locality, so it is likely that
> actually the binary search dominates for some data sets.

Galloping search ftw (good locality, log complexity). -- Andrei