[Issue 12992] Add an interpolate policy to binary search policies
via Digitalmars-d-bugs
digitalmars-d-bugs at puremagic.com
Wed Jun 25 08:07:56 PDT 2014
https://issues.dlang.org/show_bug.cgi?id=12992
--- Comment #3 from bearophile_hugs at eml.cc ---
(In reply to Andrei Alexandrescu from comment #2)
> If the element type is numeric no lambda is needed.
I don't agree or I don't understand. If you have an array of sorted integers
with a uniform distribution you need a certain interpolating function. if your
array of sorted integers has a squared distribution, you need a different
interpolating function, otherwise your search is slower than a standard binary
search. Unless the interpolated search performs a statistics on the data, the
user has to supply in both cases some kind of function that specifies that
distribution.
--
More information about the Digitalmars-d-bugs
mailing list