考研数据结构之顺序查找、折半查找与分块查找详解（包含真题及解析）

考研数据结构之顺序查找、折半查找与分块查找详解

一、顺序查找（Sequential Search）

1.1 基本思想

顺序查找是最基础的查找算法，通过遍历数据集合逐个比较目标值与当前元素，直到找到匹配项或遍历结束。其核心特点是：

• 无序性：不要求数据有序，适用于任何存储结构
• 简单性：实现逻辑直观，但平均时间复杂度为O(n)

// 伪代码示例
int SequentialSearch(int arr[], int n, int key) {for(int i=0; i<n; i++) {if(arr[i] == key) return i;}return -1;
}

1.2 适用场景

• 小规模数据集合
• 动态变化频繁的线性表
• 无法预排序的场景

---

二、折半查找（Binary Search）

2.1 核心原理

折半查找通过分治策略将搜索区间逐步缩小，要求数据必须有序且顺序存储。典型步骤：

1. 确定中间元素mid = (low + high)/2
2. 比较目标值与中间元素
3. 根据比较结果选择左/右子区间递归查找

// 递归实现示例
int BinarySearch(int arr[], int low, int high, int key) {if(low > high) return -1;int mid = (low + high) / 2;if(arr[mid] == key) return mid;else if(arr[mid] > key) return BinarySearch(arr, low, mid-1, key);else return BinarySearch(arr, mid+1, high, key);
}

2.2 性能分析

• 时间复杂度：O(log₂n)
• 空间复杂度：O(1)（非递归实现）
• 局限性：需静态有序表，插入删除成本高

---

三、分块查找（Block Search）

3.1 算法特性

分块查找结合了顺序查找和索引技术，通过分块索引表实现高效检索。其关键设计：

• 块内无序：每个数据块内部元素无需有序
• 块间有序：索引表中的块最大值保持升序排列
• 索引结构：包含块的最大关键字、起始位置等信息

3.2 实现步骤

1. 构建索引表：将数据划分为若干子块，记录每块的最大值和起始地址
2. 索引查找：在索引表中顺序/折半查找目标值所在块
3. 块内查找：在确定的块内执行顺序查找

// 分块查找伪代码框架
typedef struct {int max_key;int start_pos;
} Index;int BlockSearch(Index idx[], int block_num, int arr[], int key) {// 步骤1：索引表查找（可采用顺序或折半）int block_index = FindBlock(idx, block_num, key);if(block_index == -1) return -1;// 步骤2：块内顺序查找int start = idx[block_index].start_pos;while(arr[start] != key && start < ...) {start++;}return (arr[start] == key) ? start : -1;
}

3.3 性能平衡

• 平均查找长度：ASL = L_index + L_block
• 适用场景：大规模数据、动态变化频繁的场景

---

四、算法对比与考研重点

特性	顺序查找	折半查找	分块查找
时间复杂度	O(n)	O(logn)	O(√n)（典型情况）
空间要求	无需额外空间	需顺序存储	需索引表空间
数据要求	无序	严格有序	块间有序
动态性	支持动态插入	插入成本高	块内可动态扩展

考研高频考点：

1. 折半查找判定树的构造与ASL计算
2. 分块查找索引表的建立原则
3. 各算法适用场景的综合分析

---

五、真题解析与考点突破

6.1 顺序查找真题

题目（2023年408真题）：

若线性表采用顺序存储结构，表中元素按查找概率降序排列，查找成功时的平均查找长度为多少？

解析：

• 关键点：顺序查找的ASL计算公式为ASL = (n+1)/2，但当元素按查找概率降序排列时，概率分布不均
• 解法：设概率序列为p1 ≥ p2 ≥ ... ≥ pn，则ASL = Σ(i=1→n) i*pi
• 答案：需根据具体概率分布计算，若概率均匀分布则退化为(n+1)/2

---

6.2 折半查找真题

题目（2022年数据结构考研真题）：

在12个互异元素构成的有序数组a[1…12]中进行折半查找，若待查找元素等于a[9]，则依次与哪些元素比较？

解析：

1. 判定树构造：
   • 初始区间[1,12]，mid=6 → 比较a[6]（排除左半区）
   • 新区间[7,12]，mid=9 → 直接命中a[9]
2. 比较序列：a[6] → a[9]
3. 答案：依次比较a[6]和a[9]

---

6.3 分块查找真题

题目（严蔚敏题集改编）：

设计分块查找算法时，如何利用折半查找确定记录所在块？块内使用"监视哨"的优缺点是什么？

解析：

1. 算法设计：

   • 索引表按块最大值升序排列，使用折半查找确定目标值所在块
   • 块内采用顺序查找（可加"监视哨"优化）

2. 监视哨优缺点：

   • 优点：减少边界条件判断，提升查找效率
   • 缺点：需额外存储空间，可能破坏原数据结构
   • 实现：将目标值暂存块尾作为哨兵，循环条件改为while(arr[i] != key)

---

6.4 综合应用题

题目（2024年模拟题）：

给定长度为n的有序表，设计算法在O(1)空间复杂度下实现折半查找，并说明如何避免整数溢出

解析：

1. 非递归实现：

   int BinarySearch(int arr[], int n, int key) {int low = 0, high = n-1;while(low <= high) {int mid = low + ((high - low) >> 1); // 防溢出写法if(arr[mid] == key) return mid;else if(arr[mid] < key) low = mid + 1;else high = mid - 1;}return -1;
   }
   

2. 防溢出技巧：使用mid = low + (high - low)/2代替(low+high)/2

---

六、备考建议

1. 重点掌握：

   • 折半查找判定树的构造与ASL计算（必考）
   • 分块查找索引表与块内查找的时间复杂度关系
   • 顺序查找的概率优化策略

2. 实战技巧：

   • 遇到"查找"类大题时，优先画出判定树/索引表结构
   • 注意边界条件处理（如mid计算防溢出）
   • 熟记ASL计算公式：
     顺序查找ASL = (n+1)/2
折半查找ASL ≈ log2(n+1)-1

---

真题解析部分参考自等近年考题，建议结合《王道408真题解析》强化训练。

---