参考资料：
http://www.cnblogs.com/yw09041432/p/5908444.html
https://my.oschina.net/u/140462/blog/282319
插值与斐波那契查找都是基于2分查找的；
插值查找##
当翻字典找单词，比如“better”时，我们绝逼不是从字典中间开始找，而是，相对靠前找吧，这就是按照一定的比例来进行分割查找的过程；
折半查找，我们计算mid的方式是：
mid = (low + high) / 2， 也就是 low + 1/2 * (high - low) ;
插值将其改进成：
mid = low + (key-a[low]/a[high]-a[low])*(high-low);
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
注意
对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找不一定合适了。
特别注意： 插值中的*1.0f，避免计算机整除；
int insert_search(int a[], int key, int n) {
int low = 0;
int high = n-1;
int index = -1;
int time = 0;
while(low <= high) {
// 因计算机整除问题，需要在分母上需加入0.5
mid = low + (key-a[low])/((a[high]-a[low]) * 1.0)*(high-low);
printf("查找次数：%d, 当前mid：%d\n", ++time, mid);
if(a[mid] == key) {
index = mid;
break;
} else if(a[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return index;
}
int half_search(int array[], int key, int n) {
int low = 0;
int high = n-1;
int index = -1;
int time = 0;
while(low <= high) {
int mid = (low + high) / 2;
printf("查找次数：%d, 当前mid：%d\n", ++time, mid);
if(array[mid] == key) {
index = mid;
break;
} else if(array[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return index;
}
// 插值查找
int main(int argc, const char * argv[]) {
int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};
//int a[] = {1,19,88,109,200,230,270,299,900,1000,1001,5000,5010,5400,5900,7000,8000,8099,9012,9099,9999,10002,12093,15432};
int value = 23;
printf("插值查找\n");
int index = insert_search(a, value, 24);
if(index > -1) {
printf("找到了，下标是：%d\n", index);
}
printf("折半查找\n");
int index2 = half_search(a, value, 24);
if(index2 > -1) {
printf("找到了，下标是：%d\n", index);
}
return 0;
}
数字分布均匀时（上面的1，2，3这种）：
插值查找
查找次数：1, 当前mid：22
找到了，下标是：22
折半查找
查找次数：1, 当前mid：11
查找次数：2, 当前mid：17
查找次数：3, 当前mid：20
查找次数：4, 当前mid：22
找到了，下标是：22
不均匀时 上面的int a[] = {1,19,88,109， 如我们要找9999时，还是half快
插值查找
查找次数：1, 当前mid：14
查找次数：2, 当前mid：17
查找次数：3, 当前mid：18
查找次数：4, 当前mid：19
查找次数：5, 当前mid：20
找到了，下标是：20
折半查找
查找次数：1, 当前mid：11
查找次数：2, 当前mid：17
查找次数：3, 当前mid：20
找到了，下标是：20
还有就是 如果用插值查找，要找得数不在列表中，容易出现死循环，大家可以尝试下，查找一下 9098，死循环，解决需要加入判断，看了很多网上的博客，都没有提高如何解决死循环；解决方案如下：**
改进如下：
int insert_search(int a[], int key, int n) {
....
while(low <= high) {
// 因计算机整除问题 * 1.0f
mid = low + (key-a[low])/((a[high]-a[low]) *1.0f)*(high-low);
printf("查找次数：%d, 当前mid：%d\n", ++time, mid);
// 加入判断，这里可解决死循环问题
// 或者判断 mid 是否与上一次mid相同，如相同，直接break
if(mid < low || mid > high) {
break;
}
.....
}
return index;
}
斐波那契查找（未理解）##
斐波那契查找利用了黄金分割原理来实现。
黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89，从第3个数开始，后面的数为前面2个数的和，随着，数组长度的增加，前一个数比后一个数的值，越来越接近0.618，利用这个特性，可以将黄金比例运用到查找技术中。
黄金比例查找也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率；
斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。
在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，（如下：第一个while循环），将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
void fibonacci(int * F) {
F[0]=0;
F[1]=1;
for(int i=2;i<50;++i)
F[i]=F[i-1]+F[i-2];
}
int fibonacciSearch(int a[], int key, int n) {
int i;
int index = -1;
int F[50];
fibonacci(F);
int low = 0;
int high = n-1;
// 获取斐波那契分割数值下标
// 在斐波那契数列找一个等于略大于查找表中元素个数的数
int k=0;
while(n > F[k] -1) {
k++;
}
// 创建临时数组，长度为 F[k] - 1
int tmp[F[k] - 1];
for(i=0; i<n; i++) { // 前面填充为原数组中的内容
tmp[i] = a[i];
}
for(i = n; i<F[k]-1; ++i) { // 后面填充为原数组最后一个元素的值
tmp[i] = a[n-1];
}
for(i=0; i<F[k]-1; i++) {
printf("%d ", tmp[i]);
}
printf("\n");
while(low <= high) {
int mid = low + F[k-1]-1;
if(key < tmp[mid]) {
// 查找前半部分，高位指针移动
high = mid -1;
k--;
} else if(key > tmp[mid]) {
// 查找后半部分，高位指针移动
low=mid+1;
k-=2;
} else {
if(mid <= high) {
index = mid;
} else {
index = high;
}
break;
}
}
return index;
}
int main(int argc, const char * argv[]) {
int a[] = {0,16,24,35,47,59,62,73,88,99};
int key=35;
int index = fibonacciSearch(a, key, 10);
if(index > -1) {
printf("%d\n", index);
}
return 0;
}
网友评论