顺序表查找

试想一下，要在散落的一大堆书中找到你需要的那本有多么麻烦。碰到这种情况的人大都会考虑做一件事，那就是把这些书排列整齐，比如竖起来放置在书架上，这样根据书名，就很容易查找到需要的图书，如下图所示。

image-20200514091718036

散落的图书可以理解为一个集合，而将它们排列整齐，就如同是将此集合构造成一个线性表。我们要针对这一线性表进行查找操作，因此它就是静态查找表。

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

顺序表查找算法

顺序查找的算法实现如下。

/* 顺序查找，a为数组，n为要查找的数组长度，key为要查找的关键字 */
int Sequential_Search(int *a, int n, int key)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        if (a[i] == key)
            return i;
    }
    return 0;
}

这段代码非常简单，就是在数组a（注意元素值从下标1开始）中查看有没有关键字（key），当你需要查找复杂表结构的记录时，只需要把数组a与关键字key定义成你需要的表结构和数据类型即可。

顺序表查找优化

到这里并非足够完美，因为每次循环时都需要对i是否越界，即是否小于等于n作判断。事实上，还可以有更好一点的办法，设置一个哨兵，可以解决不需要每次让i与n作比较。看下面的改进后的顺序查找算法代码。

/* 有哨兵顺序查找 */
int Sequential_Search2(int *a, int n, int key)
{
    int i;
    /* 设置a[0]为关键字值，我们称之为“哨兵” */
    a[0] = key;    
    /* 循环从数组尾部开始 */
    i = n;         
    while (a[i] != key)
    {
        i--;
    }
    /* 返回0则说明查找失败 */
    return i;      
}

此时代码是从尾部开始查找，由于a[0]=key，也就是说，如果在a[i]中有key则返回i值，查找成功。否则一定在最终的a[0]处等于key，此时返回的是0，即说明a[1]～a[n]中没有关键字key，查找失败。

这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然，“哨兵”也不一定就一定要在数组开始，也可以在末端。

对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为O(1)，最坏的情况是在最后一位置才找到，需要n次比较，时间复杂度为O(n)，当查找不成功时，需要n+1次比较，时间复杂度为O(n)。我们之前推导过，关键字在任何一位置的概率是相同的，所以平均查找次数为(n+1)/2，所以最终时间复杂度还是O(n)。

很显然，顺序查找技术是有很大缺点的，n很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。

另外，也正由于查找概率的不同，我们完全可以将容易查找到的记录放在前面，而不常用的记录放置在后面，效率就可以有大幅提高。

有序表查找

我们如果仅仅是把书整理在书架上，要找到一本书还是比较困难的，也就是刚才讲的需要逐个顺序查找。但如果我们在整理书架时，将图书按照书名的拼音排序放置，那么要找到某一本书就相对容易了。说白了，就是对图书做了有序排列，一个线性表有序时，对于查找总是很有帮助的。

折半查找

我们在树结构的二叉树定义时，曾经提到过一个小游戏，我在纸上已经写好了一个100以内的正整数数字请你猜，问几次可以猜出来，当时已经介绍了如何最快猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找，如下图所示。

image-20200514092918142

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

假设我们现在有这样一个有序表数组{0,1,16,24,35,47,59,62,73,88,99}，除0下标外共10个数字。对它进行查找是否存在62这个数。我们来看折半查找的算法是如何工作的。

/* 折半查找 */
int Binary_Search(int *a, int n, int key)
{
    int low, high, mid;
    /* 定义最低下标为记录首位 */
    low = 1;                       
    /* 定义最高下标为记录末位 */
    high = n;                      
    while (low <= high)
    {
        /* 折半 */
        mid = (low + high) / 2;    
        /* 若查找值比中值小 */
        if (key < a[mid])          
           /* 最高下标调整到中位下标小一位 */
           high = mid - 1;        
        /* 若查找值比中值大 */
        else if (key > a[mid])     
            /* 最低下标调整到中位下标大一位 */
            low = mid + 1;         
        else
            /* 若相等则说明mid即为查找到的位置 */
            return mid;            
    }
    return 0;
}

1．程序开始运行，参数a={0,1,16,24,35,47,59,62,73,88,99}，n=10，key=62，第3～5行，此时low=1，high=10，如下图所示。

image-20200514094149524

2．第6～15行循环，进行查找。

3．第8行，mid计算得5，由于a[5]=47<key，所以执行了第12行，low=5+1=6，如下图所示。

image-20200514094833461

4．再次循环，mid=(6+10)/2=8，此时a[8]=73>key，所以执行第10行，high=8-1=7，如下图所示。

image-20200514095057184

5．再次循环，mid=(6+7)/2=6，此时a[6]=59<key，所以执行12行，low=6+1=7，如下图所示。

image-20200514095130760

6．再次循环，mid=(7+7)/2=7，此时a[7]=62=key，查找成功，返回7。

插值查找

现在我们的新问题是，为什么一定要折半，而不是折四分之一或者折更多呢？

打个比方，在英文词典里查“apple”，你下意识里翻开词典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。

同样的，比如要在取值范围0～10000之间100个元素从小到大均匀分布的数组中查找5，我们自然会考虑从数组下标较小的开始查找。

看来，我们的折半查找，还是有改进空间的。

折半查找代码的第8句，我们略微等式变换后得到：

image-20200514095358735

也就是mid等于最低下标low加上最高下标high与low的差的一半。算法科学家们考虑的就是将这个1/2进行改进，改进为下面的计算方案：

image-20200514095719805

将1/2改成了(key-a[low])/(a[high]-a[low])有什么道理呢？假设a[11]={0,1,16,24,35,47,59,62,73,88,99}，low=1，high=10，则a[low]=1，a[high]=99，如果我们要找的是key=16时，按原来折半的做法，我们需要四次才可以得到结果，但如果用新办法，(key-a[low])/(a[high]-a[low])=(16-1)/(99-1)≈0.153，即mid≈1+0.153×(10-1)=2.377取整得到mid=2，我们只需要二次就查找到结果了，显然大大提高了查找的效率。

换句话说，我们只需要在折半查找算法的代码中更改一下第8行代码如下：

mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */

就得到了另一种有序表查找算法，插值查找法。插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式(key-a[low])/(a[high]-a[low])。应该说，从时间复杂度来看，它也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似{0,1,2,2000,2001,......,999998,999999}这种极端不均匀的数据，用插值查找未必是很合适的选择。

斐波那契查找

还有没有其他办法？我们折半查找是从中间分，也就是说，每一次查找总是一分为二，无论数据偏大还是偏小，很多时候这都未必就是最合理的做法。除了插值查找，我们再介绍一种有序查找，斐波那契查找（Fibonacci Search），它是利用了黄金分割原理来实现的。

为了能够介绍清楚这个查找算法，我们先需要有一个斐波那契数列的数组，如下图所示。

image-20200514101410855

下面我们根据代码来看程序是如何运行的。

/* 斐波那契查找 */
int Fibonacci_Search(int *a, int n, int key)
{
    int low, high, mid, i, k;
    /*定义最低下标为记录首位 */
    low = 1;                          
    /*定义最高下标为记录末位 */
    high = n;                         
    k = 0;
    /* 计算n位于斐波那契数列的位置 */
    while (n > F[k] - 1)              
        k++;
    /* 将不满的数值补全 */
    for (i = n; i < F[k] - 1; i++)    
       a[i] = a[n];
    while (low <= high)
    {
        /* 计算当前分隔的下标 */
        mid = low + F[k - 1] - 1;     
        /* 若查找记录小于当前分隔记录 */
        if (key < a[mid])             
        {
            /* 最高下标调整到分隔下标mid-1处 */
            high = mid - 1;           
            /* 斐波那契数列下标减一位 */
            k = k - 1;                
        }
        /* 若查找记录大于当前分隔记录 */
        else if (key > a[mid])        
        {
            /* 最低下标调整到分隔下标mid+1处 */
            low = mid + 1;            
            /* 斐波那契数列下标减两位 */
            k = k - 2;                
        }
        else
        {
            if (mid <= n)
                /* 若相等则说明mid即为查找到的位置 */
                return mid;           
            else
                /* 若mid>n说明是补全数值，返回n */
                return n;             
        }
    }
    return 0;
}

1．程序开始运行，参数a={0,1,16,24,35,47,59,62,73,88,99}，n=10，要查找的关键字key=59。注意此时我们已经有了事先计算好的全局变量数组F的具体数据，它是斐波那契数列，F={0,1,1,2,3,5,8,13,21,......}。

image-20200514103516829

2．第6～8行是计算当前的n处于斐波那契数列的位置。现在n=10，F[6]<n<F[7]，所以计算得出k=7。

3．第9～10行，由于k=7，计算时是以F[7]=13为基础，而a中最大的仅是a[10]，后面的a[11]，a[12]均未赋值，这不能构成有序数列，因此将它们都赋值为最大的数组值，所以此时a[11]=a[12]=a[10]=99（此段代码作用后面还有解释）。

4．第11～31行查找正式开始。

5．第13行，mid=1＋F[7-1]-1=8，也就是说，我们第一个要对比的数值是从下标为8开始的。

6．由于此时key=59而a[8]=73，因此执行第16～17行，得到high=7，k=6。

image-20200514103654734

7．再次循环，mid=1＋F[6-1]-1=5。此时a[5]=47<key，因此执行第21～22行，得到low=6，k=6-2=4。注意此时k下调2个单位。

image-20200514105325805

8．再次循环，mid=6＋F[4-1]-1=7。此时a[7]=62>key，因此执行第16～17行，得到high=6，k=4-1=3。

image-20200514105358177

9．再次循环，mid=6＋F[3-1]-1=6。此时a[6]=59=key，因此执行第26～27行，得到返回值为6。程序运行结束。

如果key=99，此时查找循环第一次时，mid=8与上例是相同的，第二次循环时，mid=11，如果a[11]没有值就会使得与key的比较失败，为了避免这样的情况出现，第9～10行的代码就起到这样的作用。

斐波那契查找算法的核心在于：

1）当key=a[mid]时，查找就成功；
2）当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
3）当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。

image-20200514105518324

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

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

应该说，三种有序表的查找本质上是分隔点的选择不同，各有优劣，实际开发时可根据数据的特点综合考虑再做出选择。