传统的二分查找算法

提到二分查找，相信很多人都不陌生，大学学数据结构的时候老师都讲过，它是一种效率较高的查找方法，基于顺序存储结构的线性表，且要求表中元素按关键字有序排列。假设元素非递减排列，则常见的二分查找过程如下：

1. 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；
2. 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表；
3. 否则进一步查找后一子表。
4. 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

我们不妨把上述算法称作版本A。版本A的查找效率固然较高，因为每一次问题的规模都缩减为原来的一半。但是并不是效率最高的，那么更好的查找算法是什么？这里我先卖个关子，我们先来分析一下版本A的效率。

这是根据版本A的思路写的C++代码。

 1#include <iostream>
 2
 3using namespace std;
 4
 5/* A：数组首地址
 6 * target：查找的目标元素
 7 * low：查找范围的下界位置
 8 * high：查找范围的上界位置
 9 *
10 * 返回值：若查找成功，则返回目标元素的位置，若查找失败，则返回-1*/
11int binSearch(int * A, int target, int low, int high){
12    while(low <= high){ //每步迭代可能都要做两次比较判断，有三个分支
13        int mid = (low + high) >> 1; //以中点为轴点
14        if(target < A[mid])
15            high = mid - 1; //深入前半段[low, mid-1]继续查找 
16        else if(A[mid] < target)
17            low = mid + 1; //深入后半段[mid+1, high]继续查找
18        else 
19            return mid; //在mid处命中
20    }
21    return -1; //查找失败，返回-1
22}
23
24int main(){
25    int nums[7] = {5, 12, 23, 43, 66, 98, 100};
26    cout << binSearch(nums, 12, 0, 6) << endl;
27    return 0;
28}

要想评估一个查找算法的性能，可以看它的平均查找长度，也就是命中目标元素时所经过的平均比较次数。那么我们就来看一下版本A的平均查找长度。

当我们查找23这个元素时，初始值low = 0， high = 6。

1. 首先获取到mid = (low + high) /2 = (0 + 6) / 2 = 3，比较23和A[3]的大小，23 < A[3] = 43 吗？Yes！，所以更新high的值为mid - 1 = 2。
2. 计算mid = (low + high) / 2 = (0 + 2) / 2 = 1，比较23和A[1]的大小，23 < A[1] = 12 吗？No！A[1] = 12 < 23 吗？Yes！，所以更新 low 的值为 mid + 1 = 2。
3. 计算mid = (low + high) / 2 = (2 + 2) / 2 = 2，比较23和A[2]的大小，23 < A[2] = 23 吗？No！A[2] = 23 < 23 吗？No！所以 23 = A[2]，最后返回 23 所在的位置。
   可以看到，整个查找过程总共经历了5次比较。

用同样的方法，我们可以得出下面这个表：

用图来表示就是这样的：

当箭头指向某一元素时，说明该元素被命中，直接返回该元素的位置。虚线上的红色数字表示每次迭代需要的比较次数，而元素上方的灰底黑色数字表示命中此元素时总共经历的比较次数。这样我们不难看到，版本A的平均查找长度为 4.1。

从上图中可以看到，往左查找只需要经过1次比较，而往右查找则需要经过2次比较，但是两侧的递归深度确实一样的，这就使得算法存在极大的不平衡。同时这也说明该算法还存在改进的空间。

改进

那么该如何改进？一种思路是使得算法转向右侧和转向左侧时都经过一次比较，这样左右不就平衡了吗？话不多说，直接上代码：

 1#include <iostream>
 2
 3using namespace std;
 4
 5/* A：数组首地址
 6 * target：查找的目标元素
 7 * low：查找范围的下界位置
 8 * high：查找范围的上界位置
 9 *
10 * 返回值：若查找成功，则返回目标元素的位置，若查找失败，则返回-1*/
11int binSearch2(int * A, int target, int low, int high) {
12    high++; //让high后移一个位置
13    while (1 < high - low) {
14        int mid = (low + high) >> 1; //以中点为轴点，经比较后确定深入
15        (target < A[mid]) ? high = mid : low = mid; //查找区间为[lwo, mid-1]或[mid, high]
16    }//出口时high = low
17
18    return (target == A[low]) ? low : -1; //返回命中元素所在的位置或-1
19}
20
21int main(){
22    int nums[7] = {5, 12, 23, 43, 66, 98, 100};
23    cout << binSearch2(nums, 23, 0, 7) << endl;
24    system("pause");
25    return 0;
26}

我们来看一下算法改进后每个元素的查找长度：

以下是算法查找过程图示：

在上图中，当某一个元素只有指入的箭头，没有指出的箭头时，说明该元素被命中，进而返回该元素所处的位置。虚线上的红色数字表示每一次迭代经过的比较次数，灰底黑色数字表示函数返回该元素的位置时总共的比较次数。

我们将改进后的版本称为版本B，根据上表可以算出版本B的平均查找长度是 3.8，跟版本A相比确实有所改进。相对于版本A来说，版本B最好情况下更坏，因为版本A最好情况下只需两次比较就够了，也就是上来就命中A[mid]，而版本B总是最后才返回A[mid]；但是反过来，版本B最好情况下比版本A要好，因为版本B无论向左还是向右，都只需经过一次比较，它向左向右的成本一样高。版本B在迭代过程中最多只需次比较，再加上函数返回时进行的一次比较，故版本B最多只需进行次比较，而版本A在最坏情况下需要次比较。所以，总的来说，版本B的整体性能更加趋于稳定。

斐波那契查找算法

接下来我们再看另一种改进的思路。

既然转向左侧的成本更低，而转向右侧的成本更高，那我们为何不让算法转向左侧的次数多一点，转向右侧的次数少一点呢呢？这样不就平衡了吗？也就是说，如果之前的算法递归模型是这样的：

表面上看起来这样使得算法不平衡了，但实际上由于转向右侧的成本高，我们就减少了转向右侧的次数，这样反而使得算法左右平衡了。那么如何才能实现这种平衡呢？

其实问题的关键就在于轴点的选择，也就是我们在此前的算法中用到的「mid」，传统的二分查找，是选择线性表的中点作为轴点，而我们将算法改进后，则是将线性表的黄金分割点作为轴点，提到黄金分割，就不得不提斐契那波数列。

我们将斐契那波数列记为，其中的第k项记为，将要查找的线性表长度记为，如果，那么我们可以以第项为轴点，这时线性表的前半部分长度为，后半部分长度为，这样就可以用同样的步骤在前半部分或后半部分中查找。因此改进后的二分查找也叫「斐波那契查找算法」。

下面是实现斐契那波查找算法的代码：

 1#include <iostream>
 2
 3using namespace std;
 4
 5/*参数a：斐契那波数列中的某一个数
 6  返回值：该数在斐契那波数列中的位置*/
 7int fibLength(int a) {
 8    int f = 0, f1 = 0, f2 = 1, index = 1;
 9    if (f1 == a)
10        return 1;
11    if (f2 == a)
12        return 2;
13    while (f <= a) {
14        f = f1 + f2;
15        f1 = f2;
16        f2 = f;
17        index++;
18    }
19    return index;
20}
21
22/*参数len：斐契那波数列的长度
23  返回值：返回一个数组指针，改指针指向长度为len的数组，该数组中存放着前len个斐契那波数*/
24int * createFibSequence(int len) {
25    int * fib = new int[len];
26    if (len == 1) {
27        fib[0] = 0;
28        return fib;
29    }else if (len == 2) {
30        fib[0] = 0;
31        fib[1] = 1;
32        return fib;
33    }
34    fib[0] = 0;
35    fib[1] = 1;
36    for (int i = 2; i < len; i++) {
37        fib[i] = fib[i - 2] + fib[i - 1];
38    }
39    return fib;
40}
41
42/* A：数组首地址
43 * target：查找的目标元素
44 * low：查找范围的下界位置
45 * high：查找范围的上界位置
46 *
47 * 返回值：若查找成功，则返回目标元素的位置，若查找失败，则返回-1*/
48int fibSearch(int * A, int target, int low, int high) {
49    high++;
50    int fib_len = fibLength(high - low + 1);
51    int * fib = createFibSequence(fib_len); //创建斐契那波数列
52
53    fib_len--;
54    while (low < high)
55    {
56        while (high - low < fib[fib_len])
57            fib_len--; //通过向前顺序查找，确定形如Fib[k] - 1的轴点
58        int mid = low + fib[fib_len] - 1; //按黄金比例切分
59        if (target < A[mid]) //深入前半段[low, mid)继续查找
60            high = mid;
61        else if (A[mid] < target) //深入后半段[mid+1, low)
62            low = mid + 1;
63        else
64            return mid; //在mid处命中
65    }
66    delete[] fib; //释放斐契那波数列占用的内存
67    return -1; //查找内存
68}
69
70int main(){
71    int nums[7] = {5, 12, 23, 43, 66, 98, 100};
72
73    for (int i = 0; i < 7; i++)
74        cout << fibSearch(nums, nums[i], 0, 6) << endl;
75    system("pause");
76    return 0;
77}

在斐契那波查找算法中每个元素的查找长度：

平均查找长度为4，和版本A相比也是有所改进的。

下图是斐契那波查找算法的查找过程示意图：

斐契那波查找算法的局限性在于它并不适用于所有场合，且需要一定的额外的时间与空间来创建斐契那波数列，所以综合看来，版本B的效果较好。

欢迎关注我的微信公众号AProgrammer