Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key.

Using big-O notation, the performance of the interpolation algorithm on a data set of size N is O(N); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be O(log log N) which is better then binary search.

**Sample Code**

```
int interpolationSearch(int[] sortedArray, int toFind){
// Returns index of toFind in sortedArray, or -1 if not found
int low = 0;
int high = sortedArray.length - 1;
int mid;
while (sortedArray[low] <= toFind && sortedArray[high] >= toFind) {
mid = low +
((toFind - sortedArray[low]) * (high - low)) /
(sortedArray[high] - sortedArray[low]); //out of range is possible here
if (sortedArray[mid] < toFind)
low = mid + 1;
else if (sortedArray[mid] > toFind)
// Repetition of the comparison code is forced by syntax limitations.
high = mid - 1;
else
return mid;
}
if (sortedArray[low] == toFind)
return low;
else
return -1; // Not found
}
```

Credit: https://en.wikipedia.org/wiki/Interpolation_search