Comment #1 by bearophile_hugs — 2014-06-25T14:49:51Z
Interpolated search is nice, but it requires a knowledge of the distribution of the data. In general it's not easy to know it (and even if you know it, you need a give a lambda to the search function).
Comment #2 by andrei — 2014-06-25T15:00:15Z
(In reply to bearophile_hugs from comment #1)
> Interpolated search is nice, but it requires a knowledge of the distribution
> of the data.
That's why it's a policy chosen by the caller.
> In general it's not easy to know it (and even if you know it,
> you need a give a lambda to the search function).
If the element type is numeric no lambda is needed.
Comment #3 by bearophile_hugs — 2014-06-25T15:07:56Z
(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.
Comment #4 by andrei — 2014-06-25T15:28:57Z
(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.
Comment #5 by bearophile_hugs — 2014-06-25T15:33:02Z
(In reply to Andrei Alexandrescu from comment #4)
> I was thinking of supporting the uniform distribution assumption.
OK, then this strict assumption needs to be stated clearly in the docs.
Comment #6 by robert.schadek — 2024-12-01T16:21:38Z