3.插值查找
插值查找其实是折半查找的升级版，在我们写折半查找的时候不知道大家想过没有
为什么每次要折一半呢？1/4不行吗？1/8不行吗？这样我们就可以想到，是不是可以找到更精准的“折半”的方式来处理呢。
在折半查找中 mid=(high+low)/2; 转化一下变成：mid=low+1/2*(high-low);
我们可以看到 “(high-low)”的系数为1/2，但是我们想找一个自适应的系数以便于找到目标数与下标为mid所对应的数更加的接近，我们就要将这个系数更改掉，让程序自己去找与目标数更加接近的数。
于是我们就将程序优化成 mid=low+((key-A[low])/(A[high]-A[low]))*(high-low);
这样我们就找到这个自适应的系数了，这样查找起来也就更快。
利用插值查找 ：查找成功或者失败的时间复杂度均为O(log2(log2n))。
int search( int str[], int n, int key )
{
int low, high, mid;
low = 0;
high = n-1;
while( low <= high )
{
mid = low + (key-a[low]/a[high]-a[low])*(high-low); // 插值查找的唯一不同点
if( str[mid] == key )
{
return mid;
}
if( str[mid] < key )
{
low = mid + 1;
}
if( str[mid] > key )
{
high = mid - 1;
}
}
return -1;
}
4.斐波那契查找
斐波那契查找也是折半查找的一种改良版；斐波那契查找最主要的就是找mid这个点；
在该种查找算法中，我们要找的mid这个点为数组中的黄金分割点，要求黄金分割点
我们就要用到斐波那契数列了；我们可以看一下这个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55..........;
-
可以看出俩个规律：
1：从第三项开始每一项等于它的前两项的和；
2：数列越往后，前后两项的比值越接近0.618，也就是黄金比例的比值；
利用这两个规律我们就可以来找这个黄金分割点；我们令这个数组为F[],下标为k；
斐波那契查找的核心就是在mid前面的长度为F[k-1]-1,在mid的后面的长度为F[k-2]-1;
具体步骤：（记待查找的数组为a）
1：构建斐波那契数组；
2：找到n（a数组的长度）在斐波那契数组中的位置，并将数组补全（可用a（n-1）来补）；
3：计算mid=low+F（k-1）-1；
4：如果a[mid]>key(key为要查找的数）high=mid-1；k=k-1；（mid前面的长度）
5：如果a[mid[<key low=mid+1；k=k-2（mid后面的长度）；
6：如果a[mid]=key &&mid<=high 则返回下标值（即mid的值）；否则查找失败；
#define MAXSIZE 20
void fibonacci(int *f)
{
int i;
f[0] = 1;
f[1] = 1;
for(i=2; i < MAXSIZE; ++i)
{
f[i] = f[i-2] + f[i-1];
}
}
// n为数组a的长度
int fibonacci_search(int *a,int key,int n)
{
int low = 0;
int high = n - 1;
int mid = 0;
int k = 0;
int F[MAXSIZE];
int i;
fibonacci(F);
while( n > F[k]-1 )
{
++k;
}
for( i=n; i < F[k]-1; ++i)
{
a[i] = a[high];
}
while( low <= high )
{
mid = low + F[k-1] - 1;
if( a[mid] > key )
{
high = mid - 1;
k = k - 1;
}
else if( a[mid] < key )
{
low = mid + 1;
k = k - 2;
}
else
{
if( mid <= high )
{
return mid;
}
else
{
return high;
}
}
}
return -1;
}
