比较顺序查找、折半查找和分块查找的适用条件与查找长度,掌握折半判定树和分块索引的工作过程。
# 一、查找的基本概念
查找是在记录集合中,根据给定关键字确定是否存在目标记录,并返回其位置或关联数据。若成功,查找长度通常按与关键字进行比较或探测的次数计;失败查找也可能需要若干次比较。
平均查找长度(ASL)是所有可能查找请求所需比较次数的概率加权平均:
其中 是第 种请求的概率, 是相应查找长度。若各记录被查概率相同,成功查找时可对所有记录的查找长度取算术平均。
# 二、顺序查找
顺序查找从头到尾逐个比较,适用于无序表,也可用于有序表。无序表的失败查找必须检查全部 个元素;若 个元素被等概率成功查找,平均比较次数为
1 | int SequentialSearch(const int data[], int n, int key) { |
最好时间为 ,平均和最坏时间为 ,额外空间为 。若数据已经递增有序,当前元素大于目标时可以提前失败;这个优化不改变最坏复杂度。
# 三、折半查找
折半查找(二分查找)要求记录按关键字有序,且存储结构支持随机访问。每次比较中间元素,将候选区间缩小为左半或右半。
1 | int BinarySearch(const int data[], int n, int key) { |
每次区间规模约减半,时间复杂度为 ,迭代版本额外空间为 。若改成递归,调用栈需要 空间。链表虽有序,但访问中间结点需顺链遍历,通常不适合直接使用折半查找。
折半查找判定树以每次选出的中间记录为结点;较小关键字进入左子树,较大关键字进入右子树。对偶数长度区间,中点可以按题目约定取靠左或靠右的位置;画树时必须沿用代码的取中点规则。查找失败对应落入某个空链接位置,查找长度包括实际比较过的结点数。
# 四、分块查找
分块查找把表分成若干块,块内可以无序,但各块的关键字范围按块次序递增,并维护每块的最大关键字作为索引。查找分两步:
- 在索引表中找到第一个最大关键字不小于目标值的块。
- 在该块内部进行顺序查找。
flowchart LR
A[目标关键字] --> B[查找块索引]
B --> C[确定候选块]
C --> D[块内顺序查找]若共有 个元素、每块约有 个元素,则块数约为 。索引若使用顺序查找,平均代价约为 ;当 取约 时,平均查找代价为 。若索引有序,也可对索引折半查找,再对候选块顺序查找。
分块查找不要求块内有序,但要求块之间有序,并且索引值能正确界定目标所在的候选块。只对整张表 “分组” 而没有块间次序,不能直接使用该查找过程。
# 五、方法对比
| 方法 | 数据前提 | 平均 / 最坏时间 | 额外空间 |
|---|---|---|---|
| 顺序查找 | 无序也可 | / | |
| 折半查找 | 有序且能随机访问 | / | 迭代为 |
| 分块查找 | 块内无序、块间有序 | 约 (均衡分块) | 需维护索引 |
# 六、考场检查清单
- 顺序查找不要求关键字有序,折半查找要求有序且可随机访问。
- 二分区间更新时,找到中点后必须排除已经比较过的中点。
- 计算 ASL 时先确定是成功还是失败查找,以及各请求是否等概率。
- 分块查找先定位块,再查块内元素;两层代价都要计入。
- 判定树的形状取决于中点规则,偶数长度区间不能擅自改约定。
