查找算法：顺序查找、二分查找、插值查找、分块查找、哈希查找
查找，说白了就是在一堆数据里找到你想要的那个。我做了十几年嵌入式开发，几乎每个项目都离不开查找。从简单的传感器数据检索，到复杂的协议解析，查找算法的选择直接决定了系统的响应速度。
今天咱们就把五种最常用的查找算法掰开揉碎讲清楚。我会结合自己的项目经验，告诉你什么时候该用哪个，哪些坑千万别踩。
核心要点：没有最好的算法，只有最合适的算法。数据量大小、数据是否有序、内存限制、查找频率，这些因素决定了你的选择。
1. 顺序查找——最朴实的办法
顺序查找，就是从头到尾一个一个比。你想想看，这就像在一堆扑克牌里找红桃A，一张一张翻过去就是了。
我在项目中遇到过最典型的场景：解析一个简单的配置表，数据量不超过50条。这时候用顺序查找完全够用，代码还简单，不容易出bug。
// 顺序查找：从数组第一个元素开始逐个比较
int sequential_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 找到了，返回下标
}
}
return -1; // 没找到
}我的经验：顺序查找有个优化小技巧——把查找频率高的元素往前放。我在做菜单系统时，把最常用的功能放在列表前面，平均查找时间直接降了一半。
注意：顺序查找的时间复杂度是O(n)。数据量超过1000时，响应时间就开始变得明显了。我曾经在一个项目里用顺序查找查2000条记录，结果按键按下去要等半秒才有反应——这显然不行。
2. 二分查找——有序数据的利器
二分查找，说白了就是「猜数字」游戏。每次取中间值，比目标大就往左找，比目标小就往右找。前提是——数据必须有序。
我记得刚入行时，有个老工程师跟我说：「排序花的时间，会在查找时加倍还给你。」这话一点不假。
// 二分查找：要求数组已排序（升序）
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 可能溢出。我在32位单片机上吃过这个亏，当时查了半天才发现是整数溢出了。
二分查找的时间复杂度是O(log n)。1000条数据最多查10次，100万条数据最多查20次。效率提升非常明显。
3. 插值查找——更聪明的二分
插值查找是二分查找的升级版。二分查找每次都取中间点，而插值查找会根据目标值的大小，估算一个更可能的位置。
举个例子：你在字典里找「张」字，肯定不会从中间翻起，而是从后面翻。这就是插值查找的思路。
// 插值查找：适用于均匀分布的有序数组
int interpolation_search(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right && key >= arr[left] && key <= arr[right]) {
// 根据比例估算位置
int pos = left + (key - arr[left]) * (right - left) / (arr[right] - arr[left]);
if (arr[pos] == key) {
return pos;
} else if (arr[pos] < key) {
left = pos + 1;
} else {
right = pos - 1;
}
}
return -1;
}避坑指南：我曾经在一个温度传感器数据查找中用插值查找，结果数据分布不均匀（大部分集中在20-30度，偶尔有极端值），插值查找反而比二分查找还慢。所以，数据分布不均匀时，老老实实用二分查找。
4. 分块查找——折中方案
分块查找，就是把数据分成若干块，块内无序，块间有序。查找时先确定目标在哪个块，再在块内顺序查找。
我个人的习惯是：当数据量在几百到几千之间，内存又有限制时，分块查找是个很好的折中方案。它不需要全部排序，维护成本低。
// 分块查找的索引表结构
typedef struct {
int max_key; // 块内最大关键字
int start; // 块起始位置
int length; // 块长度
} Block;
// 分块查找
int block_search(int arr[], Block blocks[], int block_num, int key) {
// 第一步：在索引表中确定块
int block_idx = -1;
for (int i = 0; i < block_num; 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;
}我的经验：分块的大小怎么定？我一般取 sqrt(n) 左右。比如1000条数据，分成32块，每块约31条。这样索引表查找和块内查找的复杂度比较均衡。
5. 哈希查找——快到极致
哈希查找，核心思想是「通过一个函数，直接把关键字映射到存储位置」。理想情况下，时间复杂度是O(1)——一次定位，无需比较。
但现实没那么完美。不同的关键字可能映射到同一个位置，这就是「冲突」。处理冲突是哈希表设计的核心。
5.1 哈希函数设计
常用的哈希函数有：
- 直接定址法：H(key) = key，最简单，但要求key连续且范围小
- 除留余数法：H(key) = key % p，p一般取质数
- 平方取中法：先平方，再取中间几位
5.2 冲突处理方法
我项目中用得最多的是链地址法。为什么？因为嵌入式系统里，你不知道数据量会增长到什么程度，链地址法扩展性好。
// 链地址法：每个哈希槽位是一个链表
#define TABLE_SIZE 100
typedef struct Node {
int key;
int value;
struct Node *next;
} Node;
Node* hash_table[TABLE_SIZE];
// 哈希函数
int hash(int key) {
return key % TABLE_SIZE;
}
// 插入
void insert(int key, int value) {
int idx = hash(key);
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->key = key;
new_node->value = value;
new_node->next = hash_table[idx];
hash_table[idx] = new_node;
}
// 查找
int search(int key) {
int idx = hash(key);
Node *cur = hash_table[idx];
while (cur) {
if (cur->key == key) return cur->value;
cur = cur->next;
}
return -1; // 没找到
}重要提醒：哈希表的装载因子（元素个数/表大小）超过0.75时，冲突会急剧增加。我一般控制在0.5-0.7之间。超过0.7就考虑扩容，否则查找性能会从O(1)退化到O(n)。
我曾经踩过的坑：在一个通信协议解析项目中，我用哈希表存储消息ID到处理函数的映射。当时偷懒用了简单的取模哈希，结果消息ID分布不均匀，大部分冲突集中在几个槽位上。后来改用「除留余数法+取质数模数」，冲突率从30%降到了5%以下。
6. 五种算法对比总结
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 数据要求 |
|---|---|---|---|---|
| 顺序查找 | O(n) | O(n) | O(1) | 无 |
| 二分查找 | O(log n) | O(log n) | O(1) | 有序 |
| 插值查找 | O(log log n) | O(n) | O(1) | 有序且均匀分布 |
| 分块查找 | O(sqrt(n)) | O(n) | O(sqrt(n)) | 分块有序 |
| 哈希查找 | O(1) | O(n) | O(n) | 需设计哈希函数 |
最后说一句：别为了用算法而用算法。我见过有人为了炫技，在10个元素的数组上用二分查找——排序的时间都比查找本身长。合适的才是最好的。