下载掌阅APP，畅读海量书库
立即打开
查找是指给定一个值k，在含有n个结点的表中找出关键字等于给定值k的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。若在查找的同时对表做修改操作（如插入和删除），则相应的表称为动态查找表，否则称为静态查找表。
查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL定义为：
其中n是结点的个数，p i 是查找第i个结点的概率。若不特别声明，则认为每个结点的查找概率相等，即p l =p 2 =…=p n =1/n；c i 是找到第i个结点所需进行的比较次数。
顺序查找的基本思想是从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。
成功时的顺序查找的平均查找长度如下：
在等概率情况下，p i =1/n（1≤i≤n），故成功的平均查找长度为（n+…+2+1）/n=（n+1）/2，即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则需进行（n+1）次比较之后才能确定查找失败。
若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。
顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。
二分法查找又称为折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。
二分法查找的基本思想是：（设R[low，…，high]是当前的查找区间）
①确定该区间的中点位置：mid=[（low+high）/2]。
②将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下。
· 若R[mid].key＞k，则由表的有序性可知R[mid，…，n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low，…，mid-1]中。因此，新的查找区间是左子表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，则查找成功，算法结束。
③下一次查找是针对新的查找区间进行的，重复步骤①和②。
④在查找过程中，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所示。
图1-30 二分法查找58
图1-31 二分法查找35
二分法查找过程可用二叉树来描述。把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。要注意的是，判定树的形态只与表结点个数n相关，而与输入实例中R[1，…，n].key的取值无关。
设内部结点的总数为n=2 h -1，则判定树是深度为h=log 2 （n+1）的满二叉树。树中第k层上的结点个数为2 k-1 ，查找它们所需的比较次数是k。因此在等概率假设下，二分法查找成功时的平均查找长度为log 2 （n+1）-1。二分法查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度，即为[log 2 （n+1）]。二分法查找的最坏性能和平均性能相当接近。
虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。即使采用高效率的排序方法也要花费O（nlog 2 n）的时间，二分法查找只适用于顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分法查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法实现二分法查找。
分块查找（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 2 （b+1）-1+（s+1）/2≈log 2 （n/s+1）+s/2；如果以顺序查找确定块，分块查找成功时的平均查找长度为ASL2=（b+1）/2+（s+1）/2=（s 2 +2s+n）/（2s）。
注意
：当
时，ASL2取极小值
，即当采用顺序查找确定块时，应将各块中的结点数选定为
。
分块查找的优点是在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算；因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。
分块查找的主要代价是增加一个辅助数组的存储空间和将初始表分块排序的运算。
散列表又称为杂凑表，是一种非常实用的查找技术，能在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）。
· 除余法：令p是接近M的质数，设查找码为key，要求的桶号为T，计算T的散列函数为T=key%。
· 基数转换法：把查找码看作某个基数制上的整数，然后将它转换成另一基数制上的数。
· 平方取中法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。
· 折叠法：此方法将关键字分割成位数相同的几部分（最后一部分的倍数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。如果关键字位数很多，而且关键字中每一位上数字分布大致均匀时，可以采用折叠法得到哈希地址。
· 随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址，即 h（key）=random（key），其中random为伪随机函数，但要保证函数值在0到m-1之间。
两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。这种现象称为冲突或碰撞。发生冲突的两个关键字称为该散列函数的同义词。
冲突的频繁程度除与h相关外，还与表的填满程度相关。设m和n分别表示表长和表中填入的结点数，则将α=n/m定义为散列表的装填因子。α越大，表越满，冲突的机会也越大，通常取α≤1。
解决冲突的方法是设法在散列表中找一个空位，通常有两类方法处理冲突，分别是开放定址法和拉链法。前者是将所有结点均存放在散列表T[0，…，m-1]中，后者通常是将互为同义词的结点链成一个单链表，而将此链表的头指针放在散列表T[0，…，m-1]中。