2.6 查 找
2.6 查 找
查找是一种非常实用的数据处理技术，对查找算法的选择会直接影响数据处理的效率。例如我们查找电话号码时，因为电话簿中的姓名已按字母次序做了排序，因此查找起来就相当容易；反之，就会浪费很多时间。在学习查找算法时，除了理解各种算法的基本原理外，还应对各种算法进行比较和与分析，主要还是从空间和时间复杂度方面来评价。
2.6.1有关的概念和术语
1.关键字
用来识别数据元素（记录）特征的数据项。若能惟一识别某一元素的数据项称为主关键字；否则称为次关键字。查找的过程就是给它一个关键字值k与数据元素集合中元素的关键字项逐个比较的过程。如果找到一个关键字值等于k的数据元素，则查找成功；否则查找失败。
2.平均查找长度ASL
用来衡量某一查找算法的时间复杂度的平均值。
ASL= 
其中：n为表长; p
为查找第i个元素的概率; c
为查找第i个元素的比较次数
3.查找算法
在这一节中讨论的查找算法有线性查找、对分查找、分块查找、二叉排序树查找和哈希查找。前面4种查找方法都是通过与数据元素中的关键字项作比较来实现的，而哈希查找则是通过哈希函数来实现的。在教材中对上述各种算法的实现原理、算法描述以及时间和空间复杂度的分析都作了较详细的介绍，因此在这里主要对算法的特点和相互比较做一些补充说明。
2.6.2 线性查找
线性查找是一种最简单的查找方法，我们在前面关于线性表的基本操作中已作过介绍。它的基本思想是从线性表中第一个元素起，逐个比较元素中的关键字，直到找到与给定的值k相等，或是没有找到与给定值相等的元素为止。为了提高运算效率，在程序实现时在线性表的末尾设立一个“监视哨”，防止下标变量出界。在等概率情况下线性查找的平均查找长度为
ASL=
=
（n+1）
特点：算法简单、适用于顺序表和线性链表。
2.6.3 对分查找
如果线性表中元素是按关键字有序排列，可采用对分查找方法。它的基本思想是先与“中间位置”元素的关键字进行比较，若相等则查找成功，否则可以确定被查找的元素是在前半区间还是在后半区间，在此区间中再用对分查找方法继续查找。这样，每经过一次关键字比较就缩小一半查找区间。因此用对分查找方法查找线性表中的元素，它的比较次数与元素在线性表中的位置有关。
例2.22有线性表的元素关键字为（7，10，12，21，33，35，38，41，49，55，59，60，64，72，80），用对分查找线性表中各元素的比较次数为：
|
如果我们把相同比较次数的结点放在同一层次，各层之间用分支相连，可以构成一颗二叉树，称为对分查找的判定树，如图2.26所示。
从判定树可以看出，对分查找的过程恰是走了一条从根结点到被查结点的一条路径。由此可以计算对分查找的平均查找长度。
根据二叉树的性质，第k层上的结点数≤2
；深度为h的二叉树结点数n≤2
-1，可得 ASL=
=
设其中
=c(n)=
…
（h-1）
2c（n）=
…
2c（n）-c（n）=c（n）=h
用
=n+1，h=
代入得
c（n）=（n+1）
-n
因此 ASL=
=
-1
特点：要求线性表按关键字有序，只适用顺序表结构。
2.6.4分块查找
它是介于线性查找与对分查找之间的查找方法，要求线性表中元素“分块有序”。首先抽取各块中最大关键字构成一个索引表，因此索引表是递增有序的。查找分两步进行：第一步对索引表进行对分或线性查找，以确定待查元素在哪一块，第二步在确定的块中进行线性查找。
由于分块查找实际上是进行量词查找，因此整个算法的平均查找长度是两次查找的平均查找长度之和。
设线性表b块，前b-1块中元素个数为s=[n/b],第b块中元素个数小于或等于s。则分块查找的平均查找长度为
ASL
=ASL
+ASL
(b+1)-1+(s+1)/2
(n/s+1)+s/2
ASL
=ASL
+ASL
=(b+1)/2+(s+1)/2
=(s
+2s+n)/2s
其中ASL
为对分查找来确定块数，ASL
为用线性查找来确定块数。
特点：只有当线性表元素在“分块有序”条件下适用。有的构成的分块有序表每块中的元素个数不一定相等，此时在索引表中除了存放每块中元素的最大关键字外，还需存放每块中记录的初始和终止位置。本方法适用与顺序表及链表结构。
2.6.5 二叉排序树查找
由于在二叉排序树上进行插入或删除时，仅需修改指针而不需要移动元素，因此当需要对元素进行频繁的插入和删除时适用此法。我们从前面的二叉排序树的插入酸法中可知，二叉排序树的插入过程实际上是一个查找过程，它从根结点出发走一条从根到待查元素所在结点的路径。由于二叉排序树本身是一个有序结构，因此和对分查找类似，也是一个逐步缩小查找范围的过程。
在二叉排序树上进行查找时的平均查找长度和生成的二叉排序树深度及形态有关。含有相同元素值的数据集合，由于插入的先后次序不同，所构成的二叉排序树的深度和形态也不同，因而平均查找长度也不同。这是与对粉查找中的判定树不同之处。
特点：这是用树的结构进行查找的方法，适用于插入、删除频繁的情况。在生成的二叉排序树平衡度较好的情况下，它的平均查找长度与对粉查找相当。
2.6.6 哈希表技术及其查找
哈希查找是通过另外一种思路来进行查找，它企图作一个元素关键字与所在地址之间的函数关系，通过给定的关键字值从函数中直接求得元素所在地址而不用进行比较，这样就可以大大提高查找的效率，这种函数关系称为哈希函数。要实现哈希查找要解决下列三个问题。
(1) 如何建立哈希函数。
(2) 如何把元素按哈希查找要求防如一个线性表中，我们称这种表为哈希表。
(3) 当出现不同的关键字对应同一个地址时应提供解决方法，称为解决冲突方法。
1. 哈希函数
目前已提供很多种建立哈希函数的方法和种类，使用者可以根据具体情况参考选用，或者自行设计专用的函数。对哈希函数的基本要求是当用不同的关键字值通过哈希函数求得的地址应尽量均匀散列分布在哈希表的空间中，尽量少的出现冲突现象。
2. 哈希表
为了实现哈希查找，首先要把所有待查元素所设计的哈希函数关系放入一个表中，一般情况哈希表的空间较元素集合大，目的为提高查找效率。设哈希表空间大小为m，元素个数为n（n＜m），定义
称为哈希表的装填系数。建立哈希表的过程就是把表中每一个元素的关键字，代入哈希函数中求得对应得地址 ，称为哈希地址。
3. 解决冲突的方法
尽管我们在设计或选用哈希函数时希望由它得到的元素地址能散列分布在哈希表的空间中，即每一个关键字能惟一对应表中一个地址。但是一般情况是关键字可能出现的数量远大于哈希表给定的空间，这种函数映射关系有可能是出现多对一的关系。即多个关键字对应同一个地址，我们称为这种情况为冲突。解决冲突的方法是为冲突的关键字元素另外寻找一个新地址。通常采用的方法有：
(1) 线性探测再散列
（j=1，2，…，s，s≥1）
其中：
为冲突发生后求得的新地址。
为按哈希函数求得的地址。
为哈希表的长度。
这是最简单的解决冲方法，当出现冲突时就在求得的哈希地址毗邻的地址探测是否为空，若为空就将此地址作为冲突后的新地址。若不空，则继续将地址值加1（即j=2）再探测，直到找到新地址为止。其中mod m的作用是保证求得的新地址值在哈希表空间内。
(2) 平方探测再散列
（j=1，2，…，s，s≥1）
线性探测再散列的方法求得的新地址容易聚集在一起，这样往往会引起新的冲突，影响查找的效率。平方探测再散列方法在探测新地址时分为奇偶两种情况，例如第1次探测时在原地址之上加1，如果不成功，第2次探测时就变成在原地址上减1。而且随着探测次数增加（j的值增大），新地址在原地址两端散列距离越大，是元素在哈希表中的分布更趋均匀，使冲突出现的可能性减少。
(3) 随机探测再散列
（j=1，2，…，s，s≥1）
随机探测再散列是用一组随机数R
作为地址的修改值，同样可以改进线性探测方法的不足。
4.哈希查找
利用哈希表进行查找的过程是由给定的关键字k经哈希函数得到被查元素在哈希表中的地址。在理想情况下，查到此结束。但由于有可能存在冲突情况，因此对按哈希函数求得的地址中存放的是否是要求的元素也必须进行关键字的比较，若不同则按解决冲突方法寻找新地址，这样，不论查找成功与否，哈希查找必须进行1次甚至多次比较。可以看出，哈希查找过程与哈希表的生成过程是一致的。
尽管哈希查找由于要处理冲突问题仍须进行关键字的比较，使它的实际ASL不能等于零。但相比起来，它比线性查找、对分查找等方法的ASL要小。同时采用不同的解决冲突方法以及不同的装填系数
，得到的ASL也不相同。
希望大家能仔细读懂教材中的例子，再通过做练习来体会这一方法的实质。