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

Andrei Alexandrescu via Digitalmars-d digitalmars-d at puremagic.com
Wed Dec 2 08:03:11 PST 2015


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


More information about the Digitalmars-d mailing list