有序表查找 - 斐波那契查找

了解斐波那契查找之前先来了解下斐波那契额数列。

斐波那契数列，又称黄金分割数列，因数学家列昂纳多·斐波那契以兔子繁殖为例而引入，故又称为”兔子数列“，指的是这样一个数列：1、1、2、3、5、8、13、21、34、...... 在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n>=3，n属于正整数）。

斐波那契数列与黄金分割比的关系

随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887......

接下来讲解斐波那契查找算法（仅个人见解）

先来看下面这张图，F代表一个已经初始化了的斐波那契数组，F=[0,1,1,2,3,5,8,13,21,34,......]

mid为黄金分割点

我们以php语言为例：

/**
 * @param array $arr 排序后的有序数组
 * @param int $low 最低数组下标，默认是0
 * @param int $high 最高数组下标
 * @param string $keyword 要查找的关键字
 * @return int 要查找的关键字所在的索引位置，-1=没有找到
 */
1.     function fibonacciList_search($arr, $keyword, $high, $low = 0) {
2.         $k = 0;
3.         $F = [0,1,1,2,3,5,8,13,21,34,55,89,144];    // 定义一个斐波那契数组
4.         // 1】此处为什么是$F[$k]-1，而不是$F[$k]或者$F[$k]+1？ 
5.         while ($high > $F[$k] - 1)
6.             $k++;
7.         for ($i = $high; $i < $F[$k] - 1; $i++)
8.             $arr[$i] = $arr[$high];
9.         while ($low <= $high) {
10.           $mid = $low + $F[$k - 1] - 1;
11.           if ($keyword < $arr[$mid]) {
12.                $high = $mid - 1;
13.                $k = $k - 1;
14.            } else if ($keyword > $arr[$mid]) {
15.                $low = $mid + 1;
16.                $k = $k - 2; // 2】此处为什么是减2？
17.            } else {
18.                if ($mid <= $high) // 3】此处为什么要判断$mid <= $high？而不是像折半查找和插值查找那样直接返回$mid？
19.                    return $mid;
20.                else
21.                    return $high;
22.            }
23.         }
24.        return -1;
25.    }

我们先来走一遍这个代码：

1. 程序开始运行，首先定义一个数组，$arr = [0,1,2,3,4,5,6,7,8,9]，我们要查找的$keyword=4 ，$arr的数组最低下标为$low，数组最高下标为$high，$k为斐波那契数列$F的下标。

2. 第2~6行是计算当前的$high处于斐波那契数列的位置。$high=9，那么经运算得出$k=7。

3. 第7~8行，由于$k=7，$F[7]=13，而$arr中最大的仅是$arr[9]，后面的$arr[10]，$arr[11]都是不存在的，为了达到刚才计算出的$F[7]-1的的长度12的要求，所以这里要填充原数组，即$arr[10]=$arr[11]=$arr[9]=9.

4. 第9行到第23行查找正式开始。接下来就跟二分查找和插值查找没什么太大区别了，接下来要说明的就是高亮的问题部分。

1】此处为什么是$F[$k]-1，而不是$F[$k]或者$F[$k]+1？
这里我们要再次结合上面的图和斐波那契数列公式来理解。上面的图中的那一长条其实就是$arr，而$arr的总长度其实就是F[k]-1，而为什么要减1呢?
根据中间的黄金分割点mid我们把整个数组分成左分区和右分区两部分，左右分区都是不包含mid这个点的，所以左右分区要各减去这个黄金分割点的长度，这个长度当然是1，这个应该很好理解，再根据斐波那契额数列公式F[k] = F[k-1] + F[k-2]，结合一下前面说的，那么公式就变形成F[k] = (F[k-1]-1) + 2 + (F[k-2]-1)，再变形就是F[k]-1=(F[k-1]-1) + 1 + (F[k-2]-1)，中间这个1就是黄金分割点的长度，而F[k-1]-1就是左分区长度，F[k-2]-1就是右分区长度，这里就和上面图示中看到的意思一样了。到这里应该就比较清晰了吧，所以为了符合这个公式，我们要构造的数组长度就要符合F[k]-1。

2】此处为什么是减2？
由代码中的判断条件可知，这时候要搜索的关键字keyword是大于中间点mid的值的，那么keyword就会落在右分区，而根据问题1的解答中的公式得出，右分区的长度是F[k-2]-1，所以为什么减2，这就是原因。

3】此处为什么要判断$mid <= $high？而不是像折半查找和插值查找那样直接返回$mid？
因为我们之前重新构造了$arr的数组，这里就不多说了。

斐波那契查找的好处和特点：

1. 如果要查找的记录再右分区，则左分区的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂度也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏的情况，比如这里的keyword=1，那么始终都处于左分区在查找，则查找效率要低于折半查找。左分区要比右分区大嘛。

2. 折半查找在进行加法与除法运算（mid = (low+high)/2）,插值查找进行复杂的四则运算（mid=low+(high-low)*(key-a[low]/a[high]-a[low])）,而斐波那契查找只是最简单的加减法运算（mid=low+F[k-1]-1），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

所以，如果有人让你用最简单的加减法运算进行查找的话，毋庸置疑，斐波那契查找。