1.5 查找

查找是指给定一个值 k ，在含有 n 个结点的表中找出关键字等于给定值 k 的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。

查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL定义为：

其中 n 是结点的个数， p _i 是查找第 i 个结点的概率。若不特别声明，认为每个结点的查找概率相等，即 p _l = p ₂ =…= p _n =1/ n ； c _i 是找到第 i 个结点所需进行的比较次数。

1.5.1 顺序查找

顺序查找的基本思想是从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值 k 相比较。若当前扫描到的结点关键字与 k 相等，则查找成功；若扫描结束后，仍未找到关键字等于 k 的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。

成功时的顺序查找的平均查找长度如下：

在等概率情况下， p _i =1/ n (1≤ i ≤ n )，故成功的平均查找长度为( n +…+2+1)/ n =( n +1)/2，即查找成功时的平均比较次数约为表长的一半。若 k 值不在表中，则需进行（ n +1）次比较之后才能确定查找失败。

若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。

顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当 n 较大时不宜采用顺序查找。

1.5.2 二分法查找

二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。

二分法查找的基本思想是：（设 R [low,…,high]是当前的查找区间）

①确定该区间的中点位置：mid=[(low+high)/2]；

②将待查的 k 值与 R [mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下。

●　若 R [mid].key＞ k ，则由表的有序性可知 R [mid,…, n ].key均大于 k ，因此若表中存在关键字等于 k 的结点，则该结点必定是在位置mid左边的子表 R [low,…–,mid1]中。因此，新的查找区间是左子表 R [low,…,high]，其中high=mid–1。

●　若 R [mid].key＜ k ，则要查找的 k 必在mid的右子表 R [mid+1,…,high]中，即新的查找区间是右子表 R [low,…,high]，其中low=mid+1。

●　若 R [mid].key= k ，则查找成功，算法结束。

③下一次查找是针对新的查找区间进行，重复步骤（1）和（2）。

④在查找过程中，low逐步增加，而high逐步减少。如果high＜low，则查找失败，算法结束。

因此，从初始的查找区间 R [1,…, n ]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为 k 的结点，或者直至当前的查找区间为空（即查找失败）时为止。

例如我们要在{11，13，17，23，31，36，40，47，52，58，66，73，77，82，96，99}中查找58的过程如图1-30所示（粗体表示mid位置）。在上述序列中查找35的过程如图1-31所示。

二分法查找过程可用二叉树来描述。把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。要注意的是，判定树的形态只与表结点个数 n 相关，而与输入实例中 R [1,…, n ].key的取值无关。

设内部结点的总数为n=2 ^h –1，则判定树是深度为h=log ₂ （n+1）的满二叉树。树中第k层上的结点个数为2 ^{k -1} ，查找它们所需的比较次数是k。因此在等概率假设下，二分法查找成功时的平均查找长度为log ₂ (n+1)–1。二分法查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为[log ₂ (n+1)]。二分法查找的最坏性能和平均性能相当接近。

虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费 O ( n log ₂ n )的时间，二分法查找只适用于顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分法查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。

对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法实现二分法查找。

1.5.3 分块查找

分块查找（Blocking Search）又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。二分查找表由分块有序的线性表和索引表组成。表 R [1,…, n ]均分为 b 块，前 b – 1块中结点个数为 s =[ n / b ]，第 b 块的结点数允许小于等于 s ；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。

抽取各块中的最大关键字及其起始位置构成一个索引表 ID [l,…, b ]，即 ID [ i ](1≤ i ≤ b )中存放第 i 块的最大关键字及该块在表 R 中的起始位置。由于表 R 是分块有序的，所以索引表是一个递增有序表。

分块查找的基本思想是索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。

由于块内无序，只能用顺序查找。分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。如果以二分查找来确定块，则分块查找成功时的平均查找长度为ASL1=log ₂ (b+1)–1+(s+1)/2≈log ₂ (n/s+1)+s/2；如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2 =(b+1)/2+(s+1)/2=(s ² +2s+n)/(2s)。

注意 ：当s＝ 时，ASL2取极小值 ＋1，即当采用顺序查找确定块时，应将各块中的结点数选定为 。

分块查找的优点是在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。

分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。

1.5.4 散列表

散列表又称杂凑表，是一种非常实用的查找技术，能在 O (1)时间内完成查找。

将所有可能出现的关键字集合记为 U （简称全集）。实际发生（即实际存储）的关键字集合记为 K （| K |比| U |小得多）。散列方法是使用函数 h 将 U 映射到表 T [0,…, m –1]的下标上（ m = O (| U |)）。这样以 U 中关键字为自变量，以 h 为函数的运算结果就是相应结点的存储地址。从而达到在 O (1)时间内就可完成查找。

其中：

● h ： U →{0,1,2,…, m –1}，通常称h为散列函数（Hash函数）。散列函数 h 的作用是压缩待处理的下标范围，使待处理的|U|个值减少到 m 个值，从而降低空间开销。

● T 为散列表（Hash Table）。

● h ( K _i )（ K _i ∈ U ）是关键字为K _i 的结点存储地址（也称为散列值或散列地址）。

●　将结点按其关键字的散列地址存储到散列表中的过程称为散列（Hashing）。

1．常见的散列函数

●　除余法：令p是接近 M 的质数，设查找码为key，要求的桶号为 T ，计算 T 的散列函数为 T =key %。

●　基数转换法：把查找码看做是某个基数制上的整数，然后将它转换成另一基数制上的数。

●　平方取中法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。

●　折叠法：此方法将关键字分割成位数相同的几部分（最后一部分的倍数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。如果关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到哈希地址。

●　随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址，即 h (key)=random(key)，其中random为伪随机函数，但要保证函数值在0到 m –1之间。

2．冲突的解决

两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。这种现象称为冲突或碰撞。发生冲突的两个关键字称为该散列函数的同义词。

冲突的频繁程度除了与 h 相关外，还与表的填满程度相关。设 m 和 n 分别表示表长和表中填入的结点数，则将 α = n / m 定义为散列表的装填因子。 α 越大，表越满，冲突的机会也越大，通常取 α ≤1。

解决冲突的方法是设法在散列表中找一个空位，通常有两类方法处理冲突，分别是开放定址法和拉链法。前者是将所有结点均存放在散列表 T [0,…, m –1]中，后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表 T [0,…, m –1]中。

1）开放定址法

用开放定址法解决冲突的做法是当冲突发生时，使用某种探查（也称为探测）技术在散列表中形成一个探查序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止。若要插入结点，在探查到开放的地址时，则可将待插入的新结点存入该地址单元。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。

根据探查方式不同，开放定址法又可分为线性探查法和双散列函数法。

（1）线性探查法

线性探查法将散列表 T [0,…, m –1]看成一个循环向量，若初始探查的地址为 d （即 h (key)= d ），则探查序列为 d , d +l, d +2,…, m –1,0,1,…, d – 1。即探查时从地址 d 开始，首先探查 T [ d ]，然后依次探查 T [ d +1],…, T [ m – 1]，此后又循环到 T [0], T [1],…, T [ d –1]。

那么，线性探查法什么时候终止呢？一般来说，线性探查法终止于下列3种情况之一。

●　若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；

●　若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；

●　若探查到 T [d–1]时仍未发现空单元，也未找到key，则无论是查找还是插入，均意味着失败（此时表满）。

例如设记录关键码为（4，11，16，54，28，34，21），取 m =11， p =7， h(key) =key% p ，则采用线性探查法处理冲突的结果如图1-32所示。

（2）双散列函数法

由于线性探查法容易产生堆积现象，会大大降低查找效率，可用双散列函数法。双散列函数法是开放定址法中最好的方法之一，它的探查序列是：

该方法使用了两个散列函数 h (key)和 h 1(key)，故也称为双散列函数探查法。定义 h 1(key)的方法较多，但无论采用什么方法定义，都必须使 h 1( key )的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。

例如设记录关键码为（4，11，16，54，28，34，21），取 m =11， p =7， h(key) =key% p ，则采用双散列函数法处理冲突的结果如图1-33所示。

2）拉链法

用拉链法处理冲突，要求散列表的每个结点增加一个指针字段，用于链接同义词的子表，链表中的结点都是同义词。

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m ，则可将散列表定义为一个由 m 个头指针组成的指针数组 T [0,…, m –1]。凡是散列地址为 i 的结点，均插入到以 T [ i ]为头指针的单链表中。 T 中各分量的初值均应为空指针。在拉链法中，装填因子 α 可以大于1，但一般均取 α ≤1。

例如设记录关键码为（4,11,18,54,28,34,21），取 m = d =5， h(key) =key% d 。采用拉链法的结果如图1-34所示。