查找算法（一）：顺序查找、折半查找、插值查找、斐波那契查找
查找，说白了就是在一堆数据里找到你想要的那个。做嵌入式这些年，我写过无数查找代码——从传感器数据表里找阈值，从配置参数里找匹配项，甚至从固件升级包中定位特定字节。查找算法选不对，轻则响应慢半拍，重则系统直接卡死。今天咱们就把四种最基础的查找算法掰开揉碎讲清楚。
核心要点：查找算法的本质是「如何减少比较次数」。顺序查找是蛮力法，折半查找是分治法，插值和斐波那契是折半的变种——它们都在试图更聪明地缩小搜索范围。
1. 顺序查找：最笨但最可靠的方法
顺序查找就是从头到尾挨个比。我在调试一个温控系统时遇到过这种情况：数据量只有几十个点，用折半查找还得先排序，排序本身的时间开销比查找还大。最后我直接上了顺序查找，代码简单，bug也少。
// 顺序查找：返回下标，找不到返回-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;
}时间复杂度：最好O(1)，最坏O(n)，平均O(n)。
空间复杂度：O(1)。
我的经验：如果数据量小于50，顺序查找往往比折半查找更快——因为折半查找的索引计算和边界判断有额外开销。别小看这几条指令，在中断服务程序里，每一微秒都金贵。
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) / 2 在 left+right 很大时可能溢出。我见过一个同事的代码因此出了bug——在32位系统上，数组长度接近2^31时，left+right直接变成负数。所以请用 left + (right - left) / 2。
时间复杂度：O(log n)。
空间复杂度：迭代版O(1)，递归版O(log n)。
3. 插值查找：更聪明的折半
折半查找每次取正中间，但如果你知道数据分布，完全可以猜得更准。比如在字典里查「apple」，你不会从中间翻起，而是从开头附近翻。插值查找就是基于这个思想——它根据key在数据范围中的比例来估算位置。
// 插值查找
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;
}关键点：插值查找适用于数据分布均匀的有序数组。如果数据分布极不均匀（比如1, 2, 3, 100, 1000），插值查找可能退化为O(n)。我曾在处理温度传感器数据时用过它——温度值在-40到85度之间均匀分布，效果非常好。
时间复杂度：平均O(log log n)，最坏O(n)。
空间复杂度：O(1)。
4. 斐波那契查找：用黄金分割找数据
斐波那契查找是折半查找的另一种变体。它用斐波那契数列来分割数组，而不是用中点。为什么这么做？因为斐波那契分割只涉及加减法，不涉及乘除法——在早期的CPU上，加减法比乘除法快得多。
// 斐波那契查找
int fibonacci_search(int arr[], int n, int key) {
int fib2 = 0; // F(k-2)
int fib1 = 1; // F(k-1)
int fib = fib1 + fib2; // F(k)
// 找到大于等于n的最小斐波那契数
while (fib < n) {
fib2 = fib1;
fib1 = fib;
fib = fib1 + fib2;
}
int offset = -1;
while (fib > 1) {
int i = (offset + fib2) < (n - 1) ? (offset + fib2) : (n - 1);
if (arr[i] < key) {
fib = fib1;
fib1 = fib2;
fib2 = fib - fib1;
offset = i;
} else if (arr[i] > key) {
fib = fib2;
fib1 = fib1 - fib2;
fib2 = fib - fib1;
} else {
return i;
}
}
// 检查最后一个元素
if (fib1 && arr[offset + 1] == key) {
return offset + 1;
}
return -1;
}我的看法：在现代CPU上，斐波那契查找的速度优势已经不明显了——乘除法也就几个时钟周期。但如果你在做一些极端优化的场景（比如没有硬件乘法器的MCU），斐波那契查找依然有价值。
时间复杂度：O(log n)。
空间复杂度：O(1)。
5. 四种算法对比
| 算法 | 前提条件 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|---|
| 顺序查找 | 无 | O(n) | O(n) | O(1) | 小数据量、无序数据 |
| 折半查找 | 有序 | O(log n) | O(log n) | O(1) | 有序数据、通用场景 |
| 插值查找 | 有序且均匀分布 | O(log log n) | O(n) | O(1) | 均匀分布的大数据量 |
| 斐波那契查找 | 有序 | O(log n) | O(log n) | O(1) | 资源受限的嵌入式系统 |
6. 知识体系总览
下面这张图把四种查找算法的关系梳理清楚了。你可以看到，从顺序查找到斐波那契查找，核心思路是「如何更高效地缩小搜索范围」。
7. 选型建议
说了这么多，到底该用哪个？我个人的经验是这样的：
- 数据量小于50：直接上顺序查找。代码简单，没有额外开销。
- 数据量大且有序：折半查找是首选。稳定、可靠、容易理解。
- 数据量大、有序且分布均匀：试试插值查找。我在处理均匀分布的传感器数据时，插值查找比折半查找快了将近一倍。
- 资源极度受限的MCU：考虑斐波那契查找。虽然现代CPU上优势不大，但在没有硬件乘法器的8位单片机上，它确实能省下几个时钟周期。
避坑指南：我曾经在一个项目中直接用插值查找处理温度数据，结果数据分布不均匀（大部分集中在25-30度，少数在-10度和80度），查找效率还不如顺序查找。后来我改成折半查找，问题才解决。所以——选算法前，先搞清楚你的数据长什么样。
好了，这四种查找算法就讲到这里。代码我都贴出来了，建议你亲手敲一遍，跑几个测试用例。只有自己踩过坑，才能真正理解这些算法的精髓。