插值查找基于二分查找进行改进,将从中间开始的思想转变为确定key所在的区间查找。这种查找方式要求是数列要有序。
插值查找平均时间复杂度为O(loglogn),最坏情况为O(n)。
插值查找mid=low+(high-low)*(key-arr[low])/(arr[high]-arr[low]);(key-arr[low])/(arr[high]-arr[low])求出了key占区间的比,随着算法的进行,这个比不断缩小。
int
InterpolationSearch(int[] arr, int id) {int low = 0;int high = (sizeof(arr) / sizeof(int)) - 1;int mid = 0;while (low < high) {if (arr[low] == null) low += 1;else if (arr[high] == null) high -= 1;else {mid = low + ((high - low) * (id - arr[low]) / (arr[high] - arr[low]));if (id < arr[mid]) high = mid - 1;else if (id > arr[mid]) low = mid + 1;else return mid; }}return -1;
}