【概述】

黄金分割又称黄金比例，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 $1:0.618$ 或 $1.618:1$，黄金比例不仅在绘画、艺术上有着重要的审美价值，在工程上也具有极大的作用

在二分查找中，每次查找都是将查找表一分为二，无论数据是偏大还是偏小，很多时候都未必是最合适的做法

斐波那契查找，是借助斐波那契数列从第三个数开始，前后两个数的比值越来越接近 $0.618$ 的特性，对二分查找进行了改进

【基本思想】

斐波那契查找中，首先根据查找表的长度 $n$ 来计算 $n$ 这个数，在斐波那契数列的位置 $k$，然后根据斐波那契数列中第 $k$ 个位置的元素 $F[k]$，来将查找表中不满的数值补全，最后再计算 $mid$，即：

$mid=left+F[k-1]-1$

之后，将 $a[mid]$ 与 $key$ 值进行比较，根据比较结果来调整查找区间：

$key<a[mid]$：查找记录小于当前查找点，最高下标 $right$ 调整到 $mid-1$ 处，斐波那契数列下标 $k$ 相应 $-1$
$key>a[mid]$：查找记录大于当前查找点，最低下标 $left$ 调整到 $mid+1$ 处，斐波那契数列下标 $k$ 相应 $-2$
$key=a[mid]$：查找成功，此时与 $n$ 比较，来判断是查找到的数值还是补全的数值，若 $mid\leq n$ 查找成功，反之，为补全的数值，返回 $n$

【实现】

int F[N];
void Fibonacci(){ //构造斐波那契数列
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i < N; i++)
        F[i] = F[i-1] + F[i-2];
}
int fibonacciSearch (int a[], int n, int key) {
    int low = 0;
    int high = n;
  
    Fibonacci();//构造斐波那契数列
 
    int k = 0;
    while (n > F[k]-1) //计算n位于斐波那契数列的位置
        k++;
    for (int i = n; i < F[k] - 1; i++) //将数组a扩展到F[k]-1的长度
        a[i] = a[n];
  
    while (low <= high) {
        int mid = low + F[k-1] - 1;
        if (key < temp[mid]) { //查找记录小于当前查找点
            high = mid - 1;
            k--;//斐波那契数列下标-1
        }
        else if (key > temp[mid]) { //查找记录大于当前查找点
            low = mid + 1;
            k -= 2; //斐波那契数列下标-2
        }
        else {
            if (mid <= n) //查找到的位置
                return mid; 
            else          //扩展的数值
                return n;
        }
    }  
    return -1;//查找失败
}