关于斐波那契查找的疑问
先上代码，问题就在三处注释的地方，其实就是我想知道Fibonacci查找的原理，理论依据是什么。

C/C++ code

#include <iostream>#include <assert.h>#define MAXSIZE 13void Fibonacci(int *f){    f[0] = 1;    f[1] = 1;    for (int i = 2; i < MAXSIZE; i++)    {        f[i] = f[i - 1] + f[i - 2];    }}int Fibonacci_Search(int *a, int n, int key){    int low, high, mid;    low  = 1;    high = n - 1;     int k = 0;    int F[MAXSIZE];    Fibonacci(F);     //这个查找n在斐波那契数列中的位置，为什么是F[k] - 1,而不是F[k]？    while ( n > F[k] - 1 )    {        k++;    }    //这个地方，我发现被查找的数组a的长度不好计算，比如，我现在要查找31在数组a中的位置    //那么，由于n = 13， 位于斐波那契数列中的第7个数（21）和第8个数（34）之间，所以k的    //值为7，F[k] - 1就等于20，那么数组a的长度就需要是a[20]。换个数又变了，我不知道这个    //应该怎么控制？    for (int i = n; i < F[k] - 1; i++)    {        a[i] = a[high];    }        //还有这个判断，当键值小于a[mid]时，就在[low, F[k - 1] - 1]范围内查找        //当键值大于a[mid]时，就在[F[k - 2] - 1]范围内查找，这个依据是什么？    while(low <= high)    {        mid = low + F[k - 1] - 1;        if ( key < a[mid] )        {            high = mid - 1;            k = k - 1;        }        else if ( key > a[mid] )        {            low = mid + 1;            k = k - 2;        }        else        {            if ( mid <= high )            {                return mid;            }            else                return n;        }    }    return -1;}int main(void){    int a[MAXSIZE * MAXSIZE] = {5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57};    int i;    std::cout<<"input number: ";    std::cin>>i;    if ( -1 != Fibonacci_Search(a, MAXSIZE, i) )    {        std::cout<<"the number i is in the position "<<Fibonacci_Search(a, MAXSIZE, i)<<std::endl;        return 1;    }    else    {        std::cout<<"i is not found in the given array!"<<std::endl;        return 0;    }    }

[解决办法]
斐波那契算法和二分查找一个意思，二分查找中mid=(start+end)/2，而在斐波那契查找中mid是按斐波那契数列值取得。
举个例子来说，如果数组下标从0-7，一共8个元素，则二分查找以第(0+7)/2=3,即第4个元素为中间分割点，将元素为两个部分。
而斐波那契数列为1、1、2、3、5、8、13、……
f(n)=8，则以f(n-1)即第5个元素为中间分割点，将数组分隔为2个部分