插值查找(Interpolation Search)是二分查找的优化，只是针对1/2的改进
int Interpolation_Search(int *a, int n, int key) {
int low, height, mid;
low = 0;
height = n;
int k_whiler = 0;
while (low <= height) {
k_whiler++;
printf("第 %d 次查找 \n",k_whiler);
mid = low + (key - a[low])/(a[height]-a[low]) * (height - low);
if(key < a[mid]) {
height = mid - 1;
}else if (key > a[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return 0;
}
排版不行 图片来补
网友评论