查找算法-插值查找、斐波那契查找

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;
}