考研408第七章：查找总结
考研408「查找」知识点全解析
一、顺序查找
1.1 定义与基本思想
顺序查找（Linear Search）属于线性查找方法的一种，在处理无序和有序数据序列时均可应用。该算法的基本原理是从数据序列的一端开始逐步比较每一个元素，在找到目标元素之前会持续进行逐一比对操作，并在遍历完整个数据序列后结束搜索过程。
时间复杂度 ：
• 最优情况下：当目标位于数组的第一个元素时达到O(1)的时间复杂度
• 最糟糕情况下：当目标位于数组的最后一端或者未被包含于数组中时达到O(n)的时间复杂度
• 平均情况下：算法仍需执行约n次操作以达到所需结果的时间复杂度为O(n)
适用场景 ：小规模数据或无序数据。
1.2 算法实现与易错点
代码示例（C语言） ：
int sequentialSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 返回索引
}
}
return -1; // 未找到
}易错点 ：
- 边界情况判断：判断循环的终止条件是否为i < n？如果数组索引从1开始，则需要对索引范围进行相应调整。
- 哨兵元素法：建议在数组末尾添加一个哨兵元素（即令$arr[n] = key），从而减少比较操作的次数。
平均查找长度（ASL）：
• 成功的查找：每个元素被访问的次数总和取平均值为\frac{1}{n}\sum_{i=1}^{n}i = \frac{n+1}{2}；
• 不成功的查找：在最坏情况下所需的比较次数取平均值为\frac{1}{n}\sum_{i=1}^{n}i = \frac{n+1}{2}。
1.3 真题与模拟题
2023年408真题 ：
对长度为n的顺序表进行查找，若采用顺序查找法，在等概率情况下查找成功的平均查找长度为（ ）。
A. n
B. (n+1)/2
C. n/2
D. \log_2 n
答案 ：B
解析 ：平均查找长度公式为\frac{1}{n}\sum_{i=1}^{n}i = \frac{n+1}{2}。
模拟题1
int sequentialSearchWithSentinel(int arr[], int n, int key) {
arr[0] = key; // 设置哨兵
int i = n;
while (arr[i] != key) {
i--;
}
return i == n ? -1 : i; // 排除哨兵
}优化效果 ：减少一次边界判断，时间复杂度仍为O(n)。
二、二分查找
2.1 定义与适用条件
二分查找（Binary Search）基于按顺序排列的数据结构 ，通过逐步缩小潜在的查找范围来确定目标值的位置。这一过程的核心在于：每次比较后将搜索空间减半 ，从而快速定位所需数据元素的位置。其基本操作包括：确定中间位置、比较中间元素与目标值并决定下一步行动以及更新搜索区间边界以缩小查找范围。
- 找出中间位置作为基准点。
- 检查数组元素与其对应的目标值。
- 将搜索范围限定为左边或右边的部分。
时间复杂度 ：O(\log n)。
2.2 算法实现与难点
代码示例（非递归） ：
int binarySearch(int arr[], int low, int high, int key) {
while (low <= high) {
int mid = low + (high - low) / 2; // 防止溢出
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}难点与易错点 ：
- 循环终止判断：仅当
low <= high时执行才能确保所有边界元素都被检查。 - 中间值计算：中间值计算时需注意避免整数溢出以确保计算结果准确。
- 判定树性质：二分查找生成的判定树是一棵平衡二叉树；当查找成功时其平均搜索长度（ASL）等于\log_2(n) - 1。
2.3 真题与模拟题
2021年408真题 ：
在长度为12的有序列表中执行二分查找时，在无法找到目标值的情况下最多需要进行（B）次比较。
A选项表示3次即可完成任务，
B选项则表明正确答案是4次，
C选项给出5次的可能性，
D选项则认为6次是必要的。
经过计算可知，
其最大比较次数计算公式为\lceil \log_2(n+1) \rceil的结果等于4，
因此正确答案应选择B选项。
模拟题2
判定树层级：
1. 根节点（mid=3）→ 比较6>5 → 右子树
2. mid=7 → 比较6<7 → 左子树
3. mid=5 → 比较6>5 → 右子树（无元素）
查找长度：3次 ASL ：(1 \times 1 + 2 \times 2 + 3 \times 2)/5 = 1.8。
三、分块查找
3.1 定义与核心思想
分块查找（索引顺序查找）融合了顺序查找和二分查找的优势，并通过划分多个区间实现数据组织。在每个区间内部采用顺序扫描的方式进行局部搜索，在不同区间之间则应用二分法实现快速定位。
时间复杂度：
查找成功：基于平衡原则下实现的时间复杂度为 O(\sqrt{n})（其中假设块数与块内元素数量相等）
查找失败：时间为 O(\sqrt{n})
3.2 算法实现与难点
代码示例 ：
// 块间二分查找
int blockSearch(int blocks[], int blockSize, int key) {
int low = 0, high = blockSize - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (blocks[mid].max < key) low = mid + 1;
else high = mid - 1;
}
// 块内顺序查找
int start = (low - 1) * blockSize;
for (int i = start; i < start + blockSize; i++) {
if (arr[i] == key) return i;
}
return -1;
}难点 ：
- 块划分方法涉及将数据划分为独立的块组，在每一块内部数据无序的情况下通常会使用顺序查找来确定具体位置；如果相邻的两个块之间具有一定的有序性，则可以在较小区间内采用折半查找以加快查找速度。
- 在索引表的管理过程中，插入和删除操作可能会引起索引表的重新构造或调整；这些操作可能会导致查询效率出现一定的下降。
3.3 真题与模拟题
2024年408真题 ：
初始有序序列为
[1, 3, 5, 7, 9, 12, 15, 18, 22, 25](@ref)（见参考文献），采用分块查找法确定目标元素18的位置。具体步骤如下：首先将序列划分为若干个长度为3的连续子序列（即块），然后执行以下操作：
第一步：确定目标元素所在的块区间；
第二步：在该块内部进行顺序查找以获取精确位置。可选方案包括：
A. 先进行块间查找以定位目标所在的具体块区间→再在该特定块内执行顺序查找
B. 先进行顺序查找→后进行二分查找以缩小范围
C. 直接通过顺序遍历整个序列找到目标元素
D. 使用二分法直接缩小搜索范围至最小值答案：A
解析：通过先确定目标元素所在的块区间（即完成一次范围缩小），再在此基础上执行线性搜索的方式能够显著提高效率。
模拟题3 ：
题目 ：实现分块查找算法，并在block size为4的索引表中搜索元素15，请计算平均搜索长度。
解答 ：
首先确定索引表的结构，并构建基于block size为4的索引表。接着按照分块查找的方法逐步比较候选元素值与目标值15的关系。最后根据比较结果得出结论：元素15的位置及其平均搜索长度。
索引表：[5, 9, 15, 25](@ref)（块最大值）
数据块：
1-4:
5-8:
9-12:
查找步骤：
1. 块间二分查找确定块索引2（15 < 25）
2. 块内顺序查找找到索引3
ASL = (1+2+3)/4 = 1.5 四、哈希查找
4.1 定义与核心概念
哈希表基于哈希函数将关键字映射到存储位置以保证O(1)时间复杂度的查找操作其核心涉及以下几个方面：首先需要解决的关键问题是哈希函数设计这主要包括除留余数法平方取中法等常用方法其次需要考虑如何有效处理可能出现的关键字冲突为此开发了多种策略如开放定址法及其子策略线性探测和二次探测以及链地址法等多种解决冲突的方法
装填因子公式 ：\alpha = \frac{表中记录数}{哈希表长度}，一般要求\alpha < 0.75。
4.2 算法实现与难点
链地址法示例 ：
typedef struct HashNode {
int key;
struct HashNode* next;
} HashNode;
HashNode* hashTable[TABLE_SIZE] = {NULL};
void insert(int key) {
int index = key % TABLE_SIZE;
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
int search(int key) {
int index = key % TABLE_SIZE;
HashNode* current = hashTable[index];
while (current != NULL) {
if (current->key == key) return index;
current = current->next;
}
return -1;
}易错点 ：
探测方式设置：在二次探测过程中必须确保增量步长遵循1^2, -1^2, 2^2, -2^2,...的规律；否则可能导致无法覆盖全部数据元素。
删除过程：在开放定址法中进行数据记录删除时必须明确标记为"已删除"状态；否则会影响数据查找链的完整性。
4.3 真题与模拟题
2018年408算法题 ：
设计算法以识别数组中缺失的最小自然数。
参考解法 ：通过哈希表记录已出现的正整数，并从1依次检查以确定缺失值。
练习题4
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 关键字 | 15 | 22 | 30 | 8 | |||
| ASL = \frac{1+2+3+1}{4} = 1.75。 |
五、B树与B+树
5.1 定义与适用场景
二叉索引树（简称B tree）与扩展二叉索引树（简称B+ tree）属于平衡多路查找结构的一种形式，在数据库系统中具有广泛的应用。这些数据结构常用于数据库系统以及文件系统的索引结构，并且能够高效地执行范围查询操作，并支持动态的数据插入功能。
B树性质 ：
• 每个节点最多有m个子节点（阶为m）
• 所有叶子节点在同一层。
5.2 算法实现与难点
B树插入操作 ：
- 在根节点下寻找适当的目标子节点
- 如果目标子节点未被填满，则直接将其加入
- 当目标子节点已满时，则需将其分割，并更新其父结点的状态。
难点 ：
- 分裂节点策略 ：确保树的高度平衡以防止性能退化为链表。
- 范围查询优化策略 ：B+树利用叶子节点的链接结构来加速范围遍历。
5.3 真题与模拟题
2022年408真题 ：
在B树结构中，请问：每个内部结点最多容纳5个子节点，则该结点最少需要多少个子节点？
选项如下：
A. 1
B. 2
C. 3
D. 5
正确答案是选项B
详细解析：根据B树的定义，在这种情况下根结点必须具备至少两个子女以满足最低要求（即阶数m \geq 2）。因此，在这种情况下最少需要两个子女。
模拟题5 ：
题目 ：设计B+树插入算法，在3阶B树中插入序列{10, 20, 5, 6, 15, 30}，并画出最终结构。
解答 ：
根节点分裂为和
左子树插入15，右子树插入30
ASL计算略（需遍历路径） 六、哈希表冲突处理（续）
6.1 链地址法（Chaining）
采用哈希表作为核心数据结构，并使每个槽位对应一个链表的方式是链地址法的基本实现思路。具体实现如下：
核心概念：在哈希表中设计一个机制使得每一个槽位都存储一个链表。当处理碰撞情况时，则将其添加到对应槽位链表的最后一端。
代码示例 ：
typedef struct HashNode {
int key;
struct HashNode* next;
} HashNode;
HashNode* hashTable[TABLE_SIZE] = {NULL};
void insert(int key) {
int index = key % TABLE_SIZE;
HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
newNode->key = key;
newNode->next = hashTable[index];
hashTable[index] = newNode;
}
int search(int key) {
int index = key % TABLE_SIZE;
HashNode* current = hashTable[index];
while (current != NULL) {
if (current->key == key) return index;
current = current->next;
}
return -1;
}优点 ：
- 通过分散存储冲突元素来解决聚集问题：采用链表结构使得冲突元素分散存储以避免线性探测导致的聚集现象。
- 根据需求动态调整：灵活调节链表长度以适应不同的数据规模变化。
缺点 ：
内存占用较高：为实现链表操作必须存储指向节点的指针
6.2 再哈希法（Rehashing）
再哈希法通过使用多个哈希函数，逐步探测空闲位置。具体步骤如下：
基本思路：
在发生冲突的情况下，通过第二个哈希函数计算步长以重新探测位置。公式表示为：
h_i(key) = (h_1(key) + i \cdot h_2(key)) \mod m
其中h_1和h_2为两个不同的哈希函数i表示探测次数
优点 ：
- 均匀分布特性：二次哈希函数有助于减少探测序列的聚集程度。
- 高度灵活性：兼容多种不同的哈希函数组合，并适用于各种不同的数据分布模式。
缺点 ：
- 计算复杂度较高：在计算过程中需要频繁调用哈希函数，在算法运行过程中将带来较大的性能开销。
- 步长选择非常敏感：若h_2与m不互质，则可能导致探测序列出现循环现象。
6.3 双重哈希法（Double Hashing）
双重哈希技术可视为再哈希方法的一种改进方案。其核心在于通过两个相互独立的散列函数进行数据处理，并取第二个散列函数的结果作为步长增量。该算法的具体实现方式如下所示：
h_i(\text{key}) = (h_1(\text{key}) + i \cdot h_2(\text{key})) \mod m
其中h_2(\text{key})需满足与模数m互质的要求以确保良好的分摊效果。
优点 ：
- 最佳探测序列：理论上可证, 双重哈希法在最坏情况下可实现常数时间复杂度的探测。
- 有效防止元素堆积：具有更大的跳跃幅度, 双重哈希算法能够显著降低堆积程度。
缺点 ：
- 设计该哈希函数具有较高的难度：要求h_2与模数m保持互质状态。
- 存储容量扩展带来的限制问题：所有元素的哈希值必须重新计算。
6.4 扩容策略
当哈希表的负载因子α达到或超过预设阈值时（通常设定为0.7），将需要对其进行扩容操作，并对存储的所有元素进行重新计算索引以完成更新过程。具体操作包括：首先判断当前存储空间是否满足需求；如果超出，则计算出新增的空间数量并扩展内存空间；随后遍历所有现有元素并计算其新的哈希地址；最后将数据按照新地址重新存储到扩展后的数组中以完成整个过程。
- 规模扩展：通过将哈希表容量增加到当前容量的两倍，并确保新哈希表的长度为质数来实现扩容。
- 进行再计算：采用原有的哈希函数进行位置重新计算；并根据新的表长度重新设计或调整哈希函数。
示例 ：
原表长M=11，扩容后M=23（质数），重新计算所有元素位置。
优点 ：
- 保持较高的效率 ：当负载因子下降时，在平均情况下（即摊还意义上），查找、插入和删除操作的时间复杂度均接近常数阶。
- 降低潜在的碰撞：通过扩大数据存储空间的比例，在哈希表中发生碰撞的可能性得到显著降低。
缺点 ：
- 时间消耗较高：进行扩容以及重新哈希操作的时间复杂度为O(n)。
- 空间资源利用率较低：扩容操作可能导致大量的空闲槽位。
6.5 不同冲突处理方法的对比与选择
| 方法 | 时间复杂度（均摊） | 空间复杂度 | 聚集问题 | 实现复杂度 | 适用场景 |
|---|---|---|---|---|---|
| 链地址法 | O(1) | O(n) | 否 | 中等 | 冲突频繁、需动态扩容 |
| 开放定址法 | O(1)（理想） | O(n) | 是 | 低 | 冲突较少、表较小 |
| 再哈希法 | O(1) | O(n) | 否 | 高 | 需灵活探测序列 |
| 双重哈希法 | O(1) | O(n) | 否 | 中等 | 需最优探测序列 |
选择建议 ：
- 链地址法：主要用于处理高负载因子及频繁增删操作的情况。
- 开放定址法：主要应用于低负载因子及表规模较小的情形。
- 双重哈希法：特别适合于对探测序列分布均匀性要求较高的场合。
6.6 真题与模拟题
2024年408真题 ：
该哈希表使用链式冲突解决方法，在设定长度为13的情况下构建。所采用的哈希函数为H(key) = key \% 13。按照给定关键字序列依次插入{18, 14, 01, 68, 27, 55, 79}后，请完成以下任务：并绘制其哈希表结构示意图。
答案：
索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|----|---|---|---|---|---|---|---|---|---|----|----|----|----|
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|模拟题6 ：
题目 ：设计双重哈希法，哈希表长为23，哈希函数h_1(key) = key \% 23，h_2(key) = 5 - (key \% 5)，插入元素{10, 20, 30}，计算探测序列。
解答 ：
插入10：
h1=10%23=10, h2=5-0=5 → 步长5
探测位置：10+5=15 → 空 → 插入
插入20：
h1=20%23=20, h2=5-0=5 → 步长5
探测位置：20+5=25→25%23=2 → 空 → 插入
插入30：
h1=30%23=7, h2=5-0=5 → 步长5
探测位置：7+5=12 → 空 → 插入