关于查找的算法

基本概念：

被查找的对象是由一组记录组成的表或者文件，而每个记录则由若干个数据项组成，并假设每个记录都有一个能唯一标识该记录的关键字，在这种条件下，查找的定义式给定一个值k，在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。

常用的关于查找的算法有如下几种：

一、 顺序查找

顺序查找时一种最简单的查找方法。

它的基本思路是：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败。

它的优点是算法简单，缺点是查找效率低，因此当n比较大的时候，不宜采用顺序查找。

分析：其平均查找长度为 （n+1）/2

二、 二分查找

二分查找又称折半查找，是一种效率较高的查找方法。线性表示有序表，以下算法假设有序表是递增有序的

其基本思想是：设R[low…high]是当前的查找区间； （1） 首先确定区间的中点位置mid

（2） 然后将待查的k值与R[mid].key比较，若相等则查找成功并返回该位置，若不

相等，则需要确定新的查找区间。

（3） 如果R[mid].key > k，则新的查找区间为R[0…mid-1] （4） 如果R[mid].key < k，则新的查找区间为R[mid+1,n-1]

分析：其平均查找长度为：log2(n+1)-1。二分查找只适合于静态查找表，不适合动态查找表。

三、 分块查找

又称索引顺序查找，是一种性能介于顺序查找和二分查找之间的查找方法。

要求：线性表是“分块有序”的。即：将表R[0…n-1]均分为b块，前b-1块中记录个数s=(n/b)取上整数，最后一块的记录数小于等于s；每一块中的关键字不一定有序，但前一块的最大关键字必须小于后一块中的最小关键字。

其基本思想是：

（1） 抽取各块中的最大关键字及其起始位置构建一个索引表IDX[0…b-1]。因为表

示分块有序的，因此IDX[0…b-1]是有序递增的。

（2） 首先查找索引表（使用顺序或者二分查找），以确定待查的记录在哪一块。 （3） 然后在已确定的快中进行顺序查找 分析：分块查找实际上时两次查找过程，故整个查找过程的平均查找长度是两次查找的平均长度之和 为log2(n/s+1)+s/2.

四、 二插排序树

二插排序树(BST)，其定义为：或者是空树或者满足如下性质： （1） 若左子树非空，则左子树上所有记录的值均小于根记录的值 （2） 若若子树非空，则右子树上所有记录的值均小于根记录的值 （3） 左右子树本身又各是一颗二叉排序树。

按中序遍历该树得到的中序序列是一个递增的有序序列。

基本思想是：首先要构建二插排序树，之后在树上进行查找，查找的方法和二分查找很像。生产二插排序树的基本思想是：

（1） 如果排序树T为空，就创建一个key域为k的节点，作为根结点。 （2） 否则将K和根结点的关键字比较，如果二者相等，无须插入

（3） 如果k小于根结点的关键字，则将k插入根结点的左子树中，否则插入根结点

的右子树中。

其平均查找长度和树的形态有关，在最坏情况下，即原记录是有序的，此时二插树蜕变成了深度为n的单支树。则其平均查找长度为 （n+1）/2。在最好情况下，树的形态比较匀称，其平均查找长度为：log2(n).

五、 平衡二叉树

若一颗二叉树中每个结点中的左右子树的高度至多相差1，则称为平衡二插树。 在平衡二叉树上进行查找的过程和在二插排序树上进行查找的过程完全相同。 其平均查找长度为O(log2n)

六、 B-树查找

又称为多路平衡查找树，是一种组织和维护外存文件系统非常有效的数据结构。B-树中所有结点的孩子结点最大值称为B-树的阶，用m来表示，要求m>=3.

B-树的概念：或者是空树或者是满足以下要求的m树。见数据结构书P245 在一棵b-树上查找的基本概念是：

（1） 将k与根结点中的key[i]进行比较 （2） 如果k=key[i]，则查找成功；

（3） 若k（4） 若key[i]key[n]，则沿着指针ptr[n]所指的子树继续查找

七、 B+树查找

在B+数中查找可以采用两种查找方式：一种是直接从最小关键字开始进行顺序查找；另一种是从B+树的根结点开始进行随机查找。 八、哈希表查找

哈希表又称散列表，是除了顺序表存储结构、链表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。

哈希表存储的基本思路是：设要存储的对象的个数为n，设置一个长度为m(m>=n)的连续内存单元，以线性表中每个对象的关键字ki(0=但是会出现哈希冲突，即ki 不等于 kj。但是h(ki)=h(kj)。 哈希函数的构造方法：

1、 直接定址法 ：h(k)=k+c 2、 出留余数法：h(k)=k mod p

3、 数字分析法：提取关键字中的取值较均匀的数字位作为哈希地址。 解决冲突的方法：

1、 开放定址法：是一类以发生冲突的哈希地址为自变量，通过某种哈希冲突函数

得到一个新的空闲地址的方法。这里的哈希冲突函数有很多种：线性探查法和平方探查法。

2、 拉链法：把所有的同义词用单链表连接起来的方法。哈希表每个单元中存放的

不再是记录本身，而是相应同义词单链表早点头指针。

在哈希表上的查找过程和建表过程相似：

1、 假设给定的值为k，根据建表时设定的哈希函数h，计算出哈希地址h(k)。 2、 如果表中该地址单元不为空，并且该地址的关键字不等于K，则按建表时设定的处理冲突的方法找下一个地址。

3、 如此反复下去，直到某个地址单元为空（查找失败）或者关键字比较相等（查找成功）为止。