【数据结构-查找篇】7.1 顺序查找、折半查找、分块查找全面详解
查找（Search）是数据结构中最基础、最常用的操作之一。本节重点讲解静态查找表中的三种经典算法：顺序查找、折半查找（二分查找）、分块查找。
一、基本概念回顾
- 静态查找表：只进行查找操作，不插入、不删除。
- 关键字（Key）：用于标识记录的某个数据项（如学号、ID）。
- 平均查找长度（ASL – Average Search Length）：衡量查找算法效率的核心指标。
ASL = Σ (每个元素被比较的概率 × 比较次数)
二、1. 顺序查找（Sequential Search）
定义
从表的一端开始，逐个将记录的关键字与给定值比较，直到找到或遍历完整个表。
适用场景
- 线性表（顺序存储或链式存储）
- 无序表或有序表均可（但有序时可优化提前终止）
算法实现（顺序表）
int SequentialSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key)
return i; // 找到，返回下标
}
return -1; // 未找到
}优化：哨兵（Sentinel）顺序查找（减少一次判断）
int SequentialSearchWithSentinel(int arr[], int n, int key) {
arr[0] = key; // 把0位置设为哨兵（需提前备份原arr[0]）
int i = n - 1;
while (arr[i] != key)
i--;
return i; // 如果i==0说明没找到，否则返回位置
}性能分析（最坏情况相同，平均不同）
| 情况 | 查找成功 ASL | 查找失败 ASL | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 无序表 | (n+1)/2 | n | O(n) | O(1) |
| 有序表（可提前终止） | ≈ n/2（成功） | ≈ n/2（失败） | O(n) | O(1) |
优点：简单，实现容易，对数据无要求
缺点：效率低，适合小规模数据
三、2. 折半查找（Binary Search / 二分查找）
定义
前提：有序表（通常升序），每次将中间元素与关键字比较，将查找范围缩小一半。
算法实现（递归版 + 非递归版）
非递归版（推荐）
int BinarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // 避免溢出写法
// int mid = (low + high) / 2; // 传统写法，可能溢出
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1; // 未找到
}递归版
int BinarySearchRecursive(int arr[], int low, int high, int key) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
return BinarySearchRecursive(arr, mid + 1, high, key);
else
return BinarySearchRecursive(arr, low, mid - 1, key);
}性能分析
| 项目 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(log₂ n) | 每次折半，查找次数最多 ⌊log₂ n⌋ + 1 |
| 查找成功 ASL | ≈ log₂ (n+1) – 1 | |
| 查找失败 ASL | ≈ log₂ n | |
| 空间复杂度 | O(1)（非递归） / O(log n)（递归） | 递归调用栈深度 |
| 查找长度（决策树） | 高度为 ⌊log₂ n⌋ + 1 的满二叉树 |
优点：效率极高，适合大规模有序数据
缺点：必须有序，且插入/删除代价大（需保持有序）
经典变种：
- 找第一个等于 key 的位置（处理重复元素）
- 找最后一个等于 key 的位置
- 找第一个大于等于 key 的位置（lower_bound）
- 找第一个大于 key 的位置（upper_bound）
四、3. 分块查找（Block Search / Indexed Sequential Search）
定义
折中方案：兼顾顺序查找的灵活性和折半查找的高效性。
核心思想：
- 将表分成若干块（块内无序或有序，块间有序）
- 建立一个索引表（每个块的最大关键字 + 块首地址）
- 先在索引表中折半查找确定目标块
- 再在块内顺序查找
数据结构
typedef struct {
int maxKey; // 本块最大关键字
int start; // 本块在主表中的起始下标
int length; // 本块长度
} IndexNode;
IndexNode index[]; // 索引表（已按 maxKey 升序排序）
int data[]; // 主表（分块存储）查找过程
- 在索引表中用折半查找，找到 maxKey ≥ key 的块
- 在该块内顺序查找 key
性能分析（假设分为 b 块，每块 s 个元素，n = b × s）
- 索引表折半查找：O(log₂ b)
- 块内顺序查找：平均 O(s/2)
- 总 ASL ≈ log₂ b + s/2
最优分块：当 log₂ b ≈ s/2 时效率最高，即块长 s ≈ √n，块数 b ≈ √n
| 项目 | 值 |
|---|---|
| 时间复杂度 | O(√n + log₂ √n) ≈ O(√n) |
| 空间复杂度 | O(√n)（索引表） |
| ASL（最优） | ≈ 2√n |
优点：
- 比顺序查找快，比折半查找灵活（支持高效插入）
- 适合动态表（插入时只需在对应块尾插入，偶尔重建索引）
缺点：需要额外索引空间
五、三种查找算法对比总结表
| 查找方法 | 前提条件 | 时间复杂度（平均） | ASL（n=1000时近似） | 空间复杂度 | 适用场景 |
|---|---|---|---|---|---|
| 顺序查找 | 无 | O(n) | ~500 | O(1) | 小数据量、无序表 |
| 折半查找 | 有序表 | O(log₂ n) | ~10 | O(1) | 大数据量、静态有序表 |
| 分块查找 | 块间有序 | O(√n) | ~63 | O(√n) | 动态表、需频繁插入、较大规模数据 |
六、实际应用场景举例
- 顺序查找：小配置文件读取、链表查找
- 折半查找：字典序查询、标准库 lower_bound/upper_bound、Java Arrays.binarySearch
- 分块查找：数据库索引早期实现、文件系统块索引、适合“读多写少但有插入”的场景
七、总结一句话
- 顺序查找：简单粗暴，适合小数据
- 折半查找：高效极致，但要求严格有序且静态
- 分块查找：折中方案，平衡了效率与灵活性，是动态查找的良好过渡
掌握这三种算法，不仅能应对考试和面试（尤其是 ASL 计算和适用场景判断），也为后续学习散列表、二叉排序树、B树/B+树打下坚实基础。
有想看具体 ASL 计算过程、变种二分实现代码、或者动态演示的，随时告诉我，我继续拆给你看～
