### 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