数据结构：线性表的查找

查找是计算机科学中一项重要的技术，用于在数据集中查找特定元素。在实际应用中，查找是一种很常用的操作。对于一些数据量很大的实时系统，比如订票系统、互联网上的信息检索系统等，查找效率尤其重要。而不同的查找算法有着各自的优势和适用场景，了解这些算法的原理和特点，可以帮助我们在处理大规模数据时更加高效地进行查找操作。

一、查找的基本概念

在讨论具体的查找算法之前，我们首先要了解一些与查找相关的概念和术语。

1.1、查找表

查找表是由同一类型的数据元素（或记录）构成的集合。

由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构，可以利用其他的数据结构来实现，比如线性表、树表、散列表等。

1.2、关键字

关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。

若关键字可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）。反之，称用以识别若干记录地关键字为次关键字。当数据元素只有一个数据项时，其关键字即为该数据元素的值。

1.3、查找

查找是指在查找表中确定是否存在一个关键字等于给定值的数据元素（或记录）。

若表中存在关键字等于给定值的记录，则称查找成功，此时查找的结果可给出整个记录的信息，或指示该记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。

1.4、静态查找表和动态查找表

动态查找表是指在查找的同时对表进行修改操作（如插入或删除），反之则称为静态查找表。

通常，动态查找表是在查找过程中动态生成的，即在创建表时，对于给定值，若表中存在关键字等于给定值的记录，则查找成功返回；否则插入关键字等于给定值的记录。

1.5、平均查找长度

平均查找长度（Average Search Length，ASL），是指在查找成功时，需要和给定值进行比较的关键字个数的期望值。对于含有n个记录的表，查找成功时的平均查找长度为：

$$ASL=\sum_{i=1}^n P_i C_i$$

其中，$P_i$为在表中找到第i个元素的概率，且$\sum_{i=1}^n P_i=1$；$C_i$为在表中找到其关键字与给定值相等的第i个记录时，已和给定值进行过比较的关键字个数。显然，$C_i$随查找过程不同而不同。

由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。

二、线性表的查找

在查找表的组织方式中，线性表是最简单的一种。线性表常用的查找方法有3种：顺序查找、折半查找和分块查找。

2.1、顺序查找

顺序查找（Sequential Search），也称线性查找，是一种简单直观的查找算法。其查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较。若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。

2.1.1、存储结构

顺序查找不仅适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。下面只介绍以顺序表作为存储结构时，实现的顺序查找算法。在C语言中，数据元素类型和顺序表的定义如下：

// 数据元素类型
typedef struct {
    // 关键字域
    KeyType key;
    // 其他域
    InfoType otherinfo;
}ElemType;

// 顺序表
typedef struct {
    // 存储空间基地址
    ElemType *R;
    // 当前长度
    int length;
}SSTable;

2.1.2、算法实现

在此假设元素从ST.R[1]开始顺序向后存放，ST.R[0]闲置不用，查找时从表的最后开始比较。顺序查找的算法步骤为：

• 从最后一个元素起，依次比较元素值和给定值，若找到值与给定值相等的元素，则查找成功，返回该元素的序号。
• 若查遍整个顺序表都没有找到，则查找失败，返回0。

相应的的算法描述为：

// 在顺序表ST中，顺序查找其关键字等于key的数据元素。
// 若找到，则函数值为该元素在表中的位置，否则为0。
int Search_Seq(SSTable ST, KeyType key) {
    // 从后往前查找
    for(i=ST.length;i>=1;--i)
        if(ST.R[i].key==key) return i;

    return 0;
}

该算法在查找过程中每步都要检测整个表是否查找完毕，即每步都要有循环变量是否满足条件i>=1的检测。改进这个程序，可以免去这个检测过程。改进方法是查找之前先对ST.R[0]的关键字赋值key，在此，ST.R[0]起到了监视哨的作用。设置监视哨的顺序查找的算法描述如下：

// 在顺序表ST中，顺序查找其关键字等于key的数据元素。
// 若找到，则函数值为该元素在表中的位置，否则为0。
int Search_Seq(SSTable ST, KeyType key) {
    // 设置哨兵
    ST.R[0].key=key;
    // 从后往前查找
    for(i=ST.length;ST.R[i].key!=key;--i);
    return i;
}

2.1.3、算法分析

通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。实践证明，这个改进能使顺序查找在ST.length≥1000时，进行一次查找所需的平均时间几乎减少一半。当然，监视哨也可设在高下标处。上述两个算法的时间复杂度一样，为：

$$ASL=\frac{1}{n} \sum_{i=1}^n i=\frac{n+1}{2}$$

即时间复杂度为O(n)。

2.1.4、优缺点

顺序查找的优点是：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。其缺点是：平均查找长度较大，查找效率较低，所以当n很大时，不宜采用顺序查找。

2.2、折半查找

折半查找，也称二分查找（Binary Search），是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素要按关键字有序排列。（在下面及后续的讨论中，均假设顺序表是递增有序的。）

折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。

折半查找每一次查找比较都使查找范围缩小一半，与顺序查找相比，很显然会提高查找效率。

2.2.1、算法实现

为了标记查找过程中每一次的查找区间，下面分别用low和high来表示当前查找区间的下界和上界，mid为区间的中间位置。折半查找的算法步骤为：

• 设置查找区间初值，low为1，high为表长。
• 当low小于等于high时，循环执行以下操作：
  • mid取low和high的中间值；
  • 将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid；
  • 若不相等则利用中间位置记录将表对分成前、后两个子表。如果key比中间位置记录的关键字小，则high取为mid-1，否则low取为mid+1。
• 循环结束，说明查找区间为空，则查找失败，返回0。

相应的算法描述为：

// 在有序表ST中，折半查找其关键字等于key的数据元素。
// 若找到，则函数值为该元素在表中的位置，否则为0。
int Search_Bin(SSTable ST,KeyType key) {
    // 设置查找区间初始值
    low=1;
    high=ST.length;

    while(low<=high) {
        mid=(low+high)/2;
        // 找到待查元素
        if(key==ST.R[mid].key) return mid;
        // 继续在前一子表进行查找
        else if(key<ST.R[mid].key) high=mid-1;
        // 继续在后一子表进行查找
        else low=mid+1;
    }

    // 表中不存在待查元素
    return 0;
}

这里唯一需要注意的是，循环执行的条件是low<=high，而不是low<high。因为当low=high时，查找区间还有一个结点，所以也需要进行比较。

2.2.2、查找示例

已知一个包含11个数据元素的有序表为(5,16,20,27,30,36,44,55,60,67,71)，请给出折半查找关键字为27和65的数据元素的过程。

折半查找关键字key=27的过程如下图所示。

假设指针low和high分别指示待查元素所在范围的下界和上界，指针mid指示区间的中间位置，即$mid = \lfloor (low+high)/2 \rfloor$。在此例中，low和high的初值分别为1和11，即[1,11]为待查范围，mid初值为6。

首先，将给定值key=27与中间位置的数据元素的关键字ST.R[mid].key相比较，因为36>27，说明待查元素若存在，必在区间[low, mid−1]的范围内，则令指针high指向第mid−1个元素，即high=5，重新求得mid的值为3。

然后，仍以key和ST.R[mid].key相比，因为20<27，说明待查待元素若存在，必在[mid+1，high]范围内，则令指针low指向第mid+1个元素，即low=4，求得mid的新值为4。

最后，比较key和ST.R[mid].key，因为相等，则查找成功，返回所查元素在表中的序号，即指针mid的值4。

折半查找关键字key=65的过程如下图所示。

整个查找过程和查找关键字为27的过程相同，只是在最后一趟查找时，因为low>high，查找区间不存在，说明表中没有关键字等于65的元素，查找失败，返回0。

2.2.3、算法分析

折半查找过程可用二叉树来描述。树中每一结点对应表中一个记录，但结点值不是记录的关键字，而是记录在表中的位置序号。把当前查找区间的中间位置作为根，左子表和右子表分别作为根的左子树和右子树，由此得到的二叉树称为折半查找的判定树。

在前面的查找示例中，查找27时的判断树。

从该判定树可见，成功的折半查找恰好是走了一条从判定树的根到被查结点的路径，比较次数恰为该结点在树中的层次。例如，查找27的过程是一条从根到结点④的路径，需要比较3次，比较次数即为结点④所在的层次。上图中，比较1次的只有一个根结点，比较2次的有两个结点，比较3次和4次的各有四个结点。假设每个记录的查找概率相同，根据此判定树可知，对长度为11的有序表进行折半查找的平均查找长度为

$$ASL=\frac{1}{11}(1+2*2+3*4+4*4)=3$$

由此可见，折半查找法在查找成功时进行比较的关键字个数最多不超过树的深度。而判定树的形态只与表的记录个数n相关，而与关键字的取值无关，具有n个结点的判定树的深度为$\lfloor \log_2 n \rfloor + 1$。所以，对于长度为n
的有序表，折半查找法在查找成功时和给定值进行比较的关键字个数至多为$\lfloor \log_2 n \rfloor + 1$。

在前面的查找示例中，查找56时的判断树。

如果在上图所示的判定树中，为所有结点的空指针域加一个指向方形结点的指针，如下图所示。并且，称这些方形结点为判定树的外部结点（与之相对，称那些圆形结点为内部结点），那么查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较的关键字个数等于该路径上内部结点个数。

例如，查找65的过程即为走了一条从根到结点9～10的路径。因此，折半查找在查找不成功时和给定值进行比较的关键字个数最多也不超过$\lfloor \log_2 n \rfloor + 1$。

折半查找的平均查找长度

借助于判定树，很容易求得折半查找的平均查找长度。为了讨论方便起见，假定有序表的长度$n=2^h-1$，则判定树是深度为$h=\log_{2}{(n+1)}$的满二叉树。树中层次为1的结点有1个，层次为2的结点有2个，…，层次为h的结点有$2^{h-1}$个。假设表中每个记录的查找概率相等，则查找成功时折半查找的平均查找长度为

$$ASL=\sum_{i=1}^n P_i C_i=\frac{1}{n} \sum_{j=1}^h j*2^{j-1}=\frac{n+1}{n} \log_2 (n+1) -1$$

当n较大时，可有下列近似结果

$$ASL=\log_2(n+1)-1$$

因此，折半查找的时间复杂度为$O(\log_{2}{n})$。可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构。

2.2.4、优缺点

折半查找的优点是：比较次数少，查找效率高。其缺点是：对表结构要求高，只能用于顺序存储的有序表。查找前需要排序，而排序本身是一种费时的运算。同时为了保持顺序表的有序性，对有序表进行插入和删除时，平均比较和移动表中一半元素，这也是一种费时的运算。因此，折半查找不适用于数据元素经常变动的线性表。

2.3、分块查找

分块查找（Blocking Search），又称索引顺序查找，是一种性能介于顺序查找和折半查找之间的一种查找方法。

2.3.1、查找过程

在分块查找法中，除线性表本身外，还需要建立一个“索引表”。例如，下图是一个线性表及其索引表。

在该线性表中，有18个记录，将其分成3个子表$(R_1,R_2,...,R_6)$、$(R_7,R_8,...,R_{12})$、$(R_{13},R_{14},...,R_{18})$，对每个子表（或称块）建立一个索引项，其中包括两项内容：

• 指针项（指示该子表的第一个记录在表中位置）

• 关键字项（其值为该子表内的最大关键字）

索引表按关键字有序，则表有序或者分块有序。所谓“分块有序”，指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，…，依次类推。因此，分块查找过程需分两步进行。先确定待查记录所在的块（子表），然后在块中顺序查找。

假设给定值key=38，则先将key依次和索引表中各最大关键字进行比较，因为22<key<48，则关键字为38的记录若存在，必定在第二个子表中。由于同一索引项中的指针指示第二个子表中的第一个记录是线性表的第7个记录，则自第7个记录起进行顺序查找，直到ST.elem[10].key=key为止。

假设此子表中没有关键字等于key的记录（例如，key=29时自第7个记录起至第12个记录的关键字和key比较都不等），则查找不成功。

2.3.2、查找性能

因为由索引项组成的索引表按关键字有序，所以确定块的查找可以用顺序查找，亦可用折半查找，而块中记录是任意排列的，则在块中只能是顺序查找。由此，分块查找算法是顺序查找和折半查找两种算法的简单合成。

分块查找的平均查找长度为：

$$ASL_{bs}=L_b+L_w$$

其中，$L_b$为查找索引表确定所在块的平均查找长度，$L_w$为在块中查找元素的平均查找长度。

一般情况下，为进行分块查找，可以将长度为n的表均匀地分成b块，每块含有s个记录，即$b=\lfloor n/s \rfloor$；又假定表中每个记录的查找概率相等，则每块查找的概率为1/b，块中每个记录的查找概率为1/s。

顺序查找确定块

若用顺序查找确定所在块，则分块查找的平均查找长度为：

$$ASL_{bs}=L_b+L_w=\frac{1}{b} \sum_{j=1}^b j + \frac{1}{s} \sum_{i=1}^s i = \frac{b+1}{2} + \frac{s+1}{2} = \frac{1}{2}(\frac{n}{s}+s)+1$$

可见，此时的平均查找长度不仅和表长n有关，而且和每一块中的记录个数s有关。在给定n的前提下，s是可以选择的。容易证明，当s取$\sqrt{n}$时，$ASL_{bs}$取最小值$\sqrt{n}+1$。这个值比顺序查找有了很大改进，但远不及折半查找。

折半查找确定块

若用折半查找确定所在块，则分块查找的平均查找长度为：

$$ASL'_{bs} \approx \log_2 (\frac{n}{s}+1) + \frac{s}{2}$$

2.3.3、优缺点

分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。其缺点是：要增加一个索引表的存储空间并对初始索引表进行排序运算。

三、小结

查找，通常是指对查找表的查找。常用的查找表有3种：线性表、树表和散列表。其中，线性表的查找，主要包括顺序查找、折半查找和分块查找。

四、参考

《数据结构（C语言版 第2版）》

《数据结构 自考02331》