【数据结构-查找】7.1顺序查找-折半查找-分块查找

【数据结构-查找篇】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说明没找到，否则返回位置
}

性能分析（最坏情况相同，平均不同）

优点：简单，实现容易，对数据无要求 缺点：效率低，适合小规模数据

三、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);
}

性能分析

优点：效率极高，适合大规模有序数据 缺点：必须有序，且插入/删除代价大（需保持有序）

经典变种：

• 找第一个等于 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[]; // 主表（分块存储）

查找过程

性能分析（假设分为 b 块，每块 s 个元素，n = b × s）

• 索引表折半查找：O(log₂ b)
• 块内顺序查找：平均 O(s/2)
• 总 ASL ≈ log₂ b + s/2

最优分块：当 log₂ b ≈ s/2 时效率最高，即块长 s ≈ √n，块数 b ≈ √n

优点：

• 比顺序查找快，比折半查找灵活（支持高效插入）
• 适合动态表（插入时只需在对应块尾插入，偶尔重建索引）

缺点：需要额外索引空间

五、三种查找算法对比总结表

六、实际应用场景举例

• 顺序查找：小配置文件读取、链表查找
• 折半查找：字典序查询、标准库 lower_bound/upper_bound、Java Arrays.binarySearch
• 分块查找：数据库索引早期实现、文件系统块索引、适合“读多写少但有插入”的场景

七、总结一句话

• 顺序查找：简单粗暴，适合小数据
• 折半查找：高效极致，但要求严格有序且静态
• 分块查找：折中方案，平衡了效率与灵活性，是动态查找的良好过渡

掌握这三种算法，不仅能应对考试和面试（尤其是 ASL 计算和适用场景判断），也为后续学习散列表、二叉排序树、B树/B+树打下坚实基础。

有想看具体 ASL 计算过程、变种二分实现代码、或者动态演示的，随时告诉我，我继续拆给你看～