数据结构与算法71讲斐波那契查找

沉默默

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 )      // 这里为何要 -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;
}

疑问看注释，为什么要减一

mumudontcry

顶一个~~~~~~

bluecn2002

顶一个。我也研究了2天了。
调试了：数组有13，12，14，15个元素。
查找下来，发现 while( n > F[k] ) 没有出错，而且数组是13时，效率还更高一点。
不知道在什么情况下，  while( n > F[k] )  会引起程序出错或低效？