### Interpolation Search from Any Distribution

In my last blog post, I introduced interpolation search, a searching algorithm that can beat binary search asymptotically. To introduce the concept of interpolation search, I made a simplifying assumption that the underlying data came from a uniform distribution. It is still possible to use interpolation search on non-uniform distributions, as long as you have the CDF for that distribution.

Background Info

A cumulative distribution function is a function that tells you the probability that a random item from the distribution is less than or equal to a specified value.

$$ F(k) = P(X \leq k) $$ Thus, $F(k)$ can take on values in the range $[0,1]$ and it is non-descending. For a discrete uniform distribution of integers in the range $[1,10]$, the CDF looks like:

And for a continuous normal distribution, the CDF looks like:

How to get the CDF There are a number of options to get a handle on the CDF. You can find information online about your distribution, do a one-pass through your data t…

Background Info

A cumulative distribution function is a function that tells you the probability that a random item from the distribution is less than or equal to a specified value.

$$ F(k) = P(X \leq k) $$ Thus, $F(k)$ can take on values in the range $[0,1]$ and it is non-descending. For a discrete uniform distribution of integers in the range $[1,10]$, the CDF looks like:

And for a continuous normal distribution, the CDF looks like:

How to get the CDF There are a number of options to get a handle on the CDF. You can find information online about your distribution, do a one-pass through your data t…