点击这里
优质
小牛编辑
136浏览
2023-12-01
插值搜索是二进制搜索的改进变体。 该搜索算法适用于所需值的探测位置。 为使此算法正常工作,数据收集应采用有序和均匀分布的形式。
它的运行时复杂性是log 2 (log 2 n) 。
用C实现 (Implementation in C)
#include<stdio.h>
#define MAX 10
// array of items on which linear search will be conducted.
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int find(int data) {
int lo = 0;
int hi = MAX - 1;
int mid = -1;
int comparisons = 1;
int index = -1;
while(lo <= hi) {
printf("\nComparison %d \n" , comparisons ) ;
printf("lo : %d, list[%d] = %d\n", lo, lo, list[lo]);
printf("hi : %d, list[%d] = %d\n", hi, hi, list[hi]);
comparisons++;
// probe the mid point
mid = lo + (((double)(hi - lo)/(list[hi] - list[lo])) * (data - list[lo]));
printf("mid = %d\n",mid);
// data found
if(list[mid] == data) {
index = mid;
break;
} else {
if(list[mid] < data) {
// if data is larger, data is in upper half
lo = mid + 1;
} else {
// if data is smaller, data is in lower half
hi = mid - 1;
}
}
}
printf("\nTotal comparisons made: %d", --comparisons);
return index;
}
int main() {
//find location of 33
int location = find(33);
// if element was found
if(location != -1)
printf("\nElement found at location: %d" ,(location+1));
else
printf("Element not found.");
return 0;
}
如果我们编译并运行上面的程序,它将产生以下结果 -
输出 (Output)
Comparison 1
lo : 0, list[0] = 10
hi : 9, list[9] = 44
mid = 6
Total comparisons made: 1
Element found at location: 7
您可以更改搜索值并执行程序进行测试。