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