斐波那契查找

2015年12月8日, 发表于长春

如果你对本文有任何的建议或者疑问, 可以在这里给我提 Issues, 谢谢! :)

斐波那契数列：

F[0]=0,F[1]=1
F[i]=F[i-1]+F[i-2]

斐波那契查找和二分查找类似，根据斐波那契序列的特点对有序表进行分割。要求开始表中记录的个数为某个斐波那契数小1，即数组个数n=F[k]-1，即数组范围a[0]~a[F[k]-2]，设点mid = F[k-1]-1,则左半部分[0,F[k-1]-2]，右半部分[F[k-1],F[k-2]]。

此时我们可以计算，左半部分长度为F[k-1]-1,右半部分长度为F[k-2]-1。 （右=F[k]-2-(F[k-1]-1)=F[k-1]+F[k-2]-2-(F[k-1]-1)=F[k-2]-1 )

左右都满足F[k]-1的形式，这就是为什么表中记录的个数为某个斐波那契数小1。当原始表不满足时，我们可以将数组A扩展到F[k]-1的长度，不足处用A[n-1]填充，再进行搜索。

所以我们有如下划分，mid是划分点：

当key=a[mid]时，查找成功；
当key < a[mid]时，新的查找范围是第low个到第mid-1个。
当key > a[mid]时，新的查找范围是第mid+1个到第high个。

这些都很好理解，可是mid点怎么表示呢？最初一次划分很容易取得，就是F[k-1]-1（设数组大小为F[k]-1)。因为划分之后左右两边长度也都满足F[k]-1的形式，具体如下：

把划分后的右子数组单独来看，长度为F[K-2]-1,所以mid2到low的距离是F[k-3]-1，（因为当长度是F[k]-1时，mid的值是F[k-1]-1)。
左子数组，同理得mid2到low的距离是F[k-2]-1。（因为左半部分长度为F[k-1]-1）

依次类推。代码如下：

void Fib( int *F)
{
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <maxsize ; i++)
    {
        F[i]=F[i-1]+F[i-2];  
    }
}

int FibSearch(int *A,int n,int key)
{
    int *F = new int[maxsize];
    int low = 0, high = n-1;
    Fib(F);
    int k = 0;
    while ( n > F[k]-1 )
        k++;

    int *tmp = new int[F[k]-1];
    for ( int i = 0; i < n; i++)
        tmp[i] = A[i];
    for(int i = n; i < F[k]-1; i++)  
        tmp[i]=A[n-1]; //将数组A扩展到F[k]-1的长度，不足处用A[n-1]填充
    while ( low <= high )
    {
        int mid = low + F[k-1] - 1;
        if ( key < tmp[mid])
        {
            high = mid - 1;
            k -= 1;
        }
        else
        if ( key > tmp[mid])
        {
            low = mid + 1;
            k -= 2;
        }
        else
        {
            if ( mid < n )
                return mid;
            else
                return n - 1;
        }
    }
    delete[] tmp;
    return -1;
}

胡湘铭的博客

Coding and thinking!

斐波那契查找