第1章：查找基础——顺序查找、折半查找与分块查找
查找，说白了就是在一堆数据里找到你想要的那个。我做了这么多年嵌入式开发，几乎每个项目都离不开查找操作。你想想看，从通讯录里找一个人名，从配置表里查一个参数，甚至是在内存中定位一个空闲块——这些本质上都是查找问题。
今天咱们就把三种最基础的查找方法讲透。这三种方法，我敢说你在实际项目中一定会用到。
1. 顺序查找（线性查找）
这是最朴素的方法。从头到尾，一个一个比。找到了就返回位置，找不到就返回-1。
代码写起来很简单：
// 普通顺序查找
int seq_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 找到了
}
}
return -1; // 没找到
}
这个代码没问题，但每次循环都要做两次比较：一次判断 i < n，一次判断 arr[i] == key。能不能优化一下？
哨兵优化
我个人习惯用哨兵技巧。把要查找的值放在数组末尾，这样就不用每次判断下标是否越界了。
// 带哨兵的顺序查找
int seq_search_sentinel(int arr[], int n, int key) {
int i = 0;
arr[n] = key; // 把key放在末尾作为哨兵
while (arr[i] != key) {
i++;
}
if (i < n) {
return i; // 找到了
} else {
return -1; // 没找到（遇到了哨兵）
}
}
我的经验：哨兵优化在数据量大的时候效果很明显。我曾经在一个数据采集项目中，每秒要处理上万次查找，用哨兵优化后整体性能提升了约15%。别小看这15%，在实时系统里可能就是能不能跑得动的区别。
注意：使用哨兵时，要确保数组末尾有额外空间。如果数组是静态分配的，千万别越界写。我曾经见过同事因为这个bug，调试了整整一个下午。
顺序查找的时间复杂度是O(n)。数据量小的时候无所谓，但数据量大了就扛不住了。
2. 折半查找（二分查找）
如果数据是有序的，那就可以用折半查找。每次把查找范围缩小一半，效率高得多。
为什么能这么做？因为有序数组有个性质：中间元素把数组分成了左右两半，根据key和中间元素的大小关系，可以确定key在哪一半。
// 折半查找（非递归版本）
int binary_search(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
关键点：mid的计算用 left + (right - left) / 2 而不是 (left + right) / 2。为什么？因为 left + right 可能溢出。我见过有人用后者，在数组很大的时候出了bug，查了半天才发现是整数溢出。
折半查找的时间复杂度是O(log n)。你想想看，100万个数据，顺序查找最坏要比较100万次，折半查找最多只需要20次。差距就是这么大。
递归版本也可以写，但我建议用非递归。递归有函数调用开销，而且深度大了可能栈溢出。
// 折半查找（递归版本，仅供参考）
int binary_search_recursive(int arr[], int left, int right, int key) {
if (left > right) return -1;
int mid = left + (right - left) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key)
return binary_search_recursive(arr, mid + 1, right, key);
else
return binary_search_recursive(arr, left, mid - 1, key);
}
避坑指南：折半查找的前提是数组有序。如果数据是无序的，千万别用。我曾经在一个项目中，接手了别人的代码，里面用了二分查找但数据没排序，结果查出来的结果时对时错，排查了很久才发现问题。
3. 分块查找（索引顺序查找）
分块查找是顺序查找和折半查找的折中方案。它把数据分成若干块，块内无序，块间有序。什么意思呢？就是第i块的所有元素都小于第i+1块的所有元素。
查找时分两步：
- 先用折半查找（或顺序查找）在索引表中定位到哪一块
- 再在块内用顺序查找
来看代码实现：
// 分块查找
#define BLOCK_SIZE 4 // 每块大小
typedef struct {
int max_key; // 块内最大关键字
int start; // 块在数组中的起始位置
int length; // 块的长度
} Block;
int block_search(int arr[], Block blocks[], int block_count, int key) {
// 第一步：在索引表中查找所属块
int block_idx = -1;
for (int i = 0; i < block_count; i++) {
if (key <= blocks[i].max_key) {
block_idx = i;
break;
}
}
if (block_idx == -1) return -1; // 超出范围
// 第二步：在块内顺序查找
Block *b = &blocks[block_idx];
for (int i = b->start; i < b->start + b->length; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
分块查找的时间复杂度介于O(log n)和O(n)之间。具体取决于块的大小和索引表的查找方式。
我的建议：分块查找适合数据量大、但数据本身是动态变化的情况。比如一个在线用户列表，用户不断上下线，但整体上按某种规则分组（比如按IP段）。这时候用分块查找，维护成本比完全排序低得多。
三种查找方法对比
| 查找方法 | 时间复杂度 | 空间复杂度 | 数据要求 | 适用场景 |
|---|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无 | 小数据量、无序数据 |
| 折半查找 | O(log n) | O(1) | 有序 | 大数据量、静态有序数据 |
| 分块查找 | O(log n) ~ O(n) | O(m)（m为块数） | 块间有序 | 动态数据、分块管理 |
知识体系图
下面这张图展示了三种查找方法的核心逻辑和关系：
实际项目中的选择建议
说了这么多，到底该用哪种？我根据经验给你几个参考：
- 数据量小于100：直接用顺序查找。代码简单，维护方便，性能差异可以忽略。
- 数据量大且基本不变：用折半查找。比如一个固定的配置表、字典表。
- 数据量大且频繁增删：考虑分块查找或者后面会讲到的哈希表。分块查找的维护成本比完全排序低。
- 数据无序且无法排序：只能顺序查找。但可以考虑用哈希表优化（后面章节会讲）。
最后说一句：查找算法是数据结构的基础，但也是实际项目中最常用的操作。我见过很多新手一上来就追求高大上的算法，结果在简单场景下反而把代码搞复杂了。记住：没有最好的算法，只有最合适的算法。
公众号：蓝海资料掘金营，微信 deep3321