[Issue 12992] Add an interpolate policy to binary search policies

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=12992

--- Comment #4 from Andrei Alexandrescu <andrei at erdani.com> ---
(In reply to bearophile_hugs from comment #3)
> (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.

I was thinking of supporting the uniform distribution assumption.

--