关于斐波那契查找的疑问
先上代码，问题就在三处注释的地方，其实就是我想知道Fibonacci查找的原理，理论依据是什么。
#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; } }