Interpolation Search:
http://en.wikipedia.org/wiki/Interpolation_search
public 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 }