软考 - 查找

一、顺序查找

顺序查找又称线性查找；

顺序查找的基本思想是从查找表的一端开始，向另一端逐个按给定值k与关键字进行比较。若找到，则查找成功，并给出记录在表中的位置；若整个表检测完，仍未找到与k相同的关键字，则查找失败，给出失败信息(返回-1)。

顺序查找的时间效率：查找成功时：(n+1)/2；查找不成功时：(n+1)

顺序查找的缺点是当n很大时，平均查找长度较大、效率低；其优点是对表中记录的存储没有要求。此外，对于链表，只能进行顺序查找。

二、折半查找

折半查找又称二分查找；

采用折半查找的前提：查找序列是有序序列；折半查找的基本思想是在有序表中取中间元素作为比较对象。若给定值k与中间记录的关键字相等，则查找成功；若给定值k小于中间记录的关键字，则在表的左半区继续查找；若给定值k大于中间记录的关键字，则在表的右半区继续查找。重复上述查找过程，直到查找成功，或所查找的区域无记录，查找失败。算法步骤如下：

1. low = 0; high = n-1; // 设置初始区间
2. 当low>high时，返回查找失败信息 // 表空，查找失败
3. 当low≤high时，mid = (low + high) / 2 // 取中点

• 若k < r[mid].key，high = mid - 1,转2 // 查找在左半区进行
• 若k > r[mid].key，low = mid +1,转2 // 查找在右半区进行
• 若k = r[mid].key，返回记录在表中的位置 // 查找成功

折半查找的时间效率为O(log₂n)

三、分块查找

分块查找又称分块索引查找，是对顺序查找的一种改进；

分块查找的性能介于顺序查找和折半查找之间，适用于对关键字分块有序的查找表进行查找操作。分块有序是指查找表可按关键字大小分成若干子表(或称块)，且前一块中的最大关键字小于后一块中的最小关键字，但是各块内部的关键字不一定有序。分块查找需对子表建立索引表，查找表的每一个子表由索引表中的索引项确定。索引项包括关键字字段(存放对应子表中的最大关键字值)和指针字段(存放子表的起始序号)两个字段。
分块查找过程分两步进行：

1. 确定要查找的记录所在的子表。用给定值k在索引表中查找索引项，以确定要查找的记录位于哪个子表中。
2. 确定要查找的记录的情况。对第1步确定的子表进行顺序查找，以确定要查找的记录的情况。

分块查找的时间效率为log₂(m+1)+n/2m

四、哈希查找

对于n个记录的集合，总能找到关键字与存放地址之间的对应函数。例如关键字类型为整型时，若最大关键字为m，则可以分配m个记录存放单元，选取函数f(key) = key即可。但是这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。通常，由于关键字的集合比Hash地址集合大得多，因此经过Hash函数变换后，可能将不同得关键字映射到同一个Hash地址上。这种现象称为冲突，映射到同一Hash地址上得关键字称为同义词。由于冲突不可能避免，只能尽可能减少；因此Hash方法需要解决以下两个问题：

1. 构造好的Hash函数
   首先，所选函数应当尽可能简单，以便提高转换速度。其次，所选函数对关键字计算出的地址应在Hash地址集中大致均匀分布，以尽量减少冲突。
2. 指定解决冲突的方案
   产生冲突主要与以下3个因素有关：

• Hash函数：若Hash函数选择得当，则可使Hash地址尽可能均匀地分布在Hash地址空间上，从而减少冲突的发生。否则，若Hash函数选择不当，则可能使Hash地址集中于某些区域，从而加大冲突的发生。
• 处理冲突的方法：由于选择适当的Hash函数可以减少冲突，但不能避免冲突；因此当冲突发生时，必须有较好的处理冲突的方法
• Hash表的装填因子。

Hash表的构造

1. 常用的Hash函数：

a. 直接定址法：
b. 除留余数法：
c. 数字分析法：
d. 平方取中法：
e. 折叠法

2. 处理冲突的方法：

a. 开放定址法：
b. 链地址法：