查找算法：从顺序到二分，再到插值与斐波那契
查找，说白了就是在一堆数据里找到你想要的那个。我做了这么多年嵌入式，几乎每个项目都离不开查找。从最简单的传感器数据检索，到复杂的协议解析，查找算法选得好不好，直接决定了系统响应快不快。
今天咱们就把查找这块彻底聊透。我会从最基础的顺序查找讲起，然后一步步深入到折半查找、插值查找和斐波那契查找。嗯，每个算法我都会结合自己的项目经验，告诉你什么时候该用，什么时候千万别用。
顺序查找：最朴素的暴力法
顺序查找的思路简单到不能再简单：从头到尾，一个一个比。找到了就返回位置，找不到就返回失败。
但这里有个坑——每次循环都要判断下标是否越界。你想想看，一个长度为n的数组，最坏情况下要比较n次元素，还要比较n次下标。这多出来的n次比较，在数据量大的时候可不是小数目。
哨兵优化：少一半比较
我在一个数据采集项目中遇到过这种情况：传感器每秒产生上千个数据点，需要实时查找特定值。用普通顺序查找，CPU负载一直下不来。后来我用了哨兵优化，效果立竿见影。
哨兵优化的核心思想很简单：把要查找的值先放到数组末尾，这样循环时就不用判断下标了，反正一定能找到。找到后检查一下位置，如果是在末尾，那就是没找到。
// 普通顺序查找
int seq_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}
// 哨兵优化版
int seq_search_sentinel(int arr[], int n, int key) {
int i = 0;
arr[n] = key; // 放置哨兵
while (arr[i] != key) i++;
return (i < n) ? i : -1;
}关键区别：普通版每次循环要判断两次（i<n 和 arr[i]==key），哨兵版只判断一次（arr[i]!=key）。数据量越大，优势越明显。
我的经验：哨兵优化在嵌入式场景特别实用。因为嵌入式CPU通常没有复杂的分支预测，减少一次判断就能省下好几个时钟周期。我曾经在一个Cortex-M3的芯片上测试过，10000个数据的查找，哨兵版快了将近30%。
注意：使用哨兵优化时，数组必须预留一个额外位置。如果你在栈上定义数组，记得把大小设为 n+1。我曾经因为忘记这个细节，导致踩内存，查了整整一个下午的bug。
折半查找：有序数据的利器
折半查找，也叫二分查找。前提条件很明确：数据必须有序。每次取中间值比较，如果比key大，就去左半边找；比key小，就去右半边找。每次排除一半数据，效率极高。
时间复杂度O(log n)，这意味着1000个数据最多查10次，100万个数据最多查20次。相比之下，顺序查找100万个数据最坏要查100万次。差距就是这么悬殊。
迭代实现：最常用的写法
int binary_search_iter(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位系统上就踩过这个坑，当时数组长度接近2^31，left+right直接变成了负数，mid算出来完全不对。
递归实现：代码更优雅
int binary_search_rec(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_rec(arr, mid + 1, right, key);
else
return binary_search_rec(arr, left, mid - 1, key);
}迭代 vs 递归：迭代版没有函数调用开销，性能更好。递归版代码更简洁，但每次递归都要压栈，深度大了可能栈溢出。我个人习惯在嵌入式开发中用迭代版，在算法演示或教学时用递归版。
插值查找：更聪明的二分
折半查找每次取中间位置，但你想过没有——如果数据分布比较均匀，我们能不能猜一个更接近的位置？比如在字典里查"zoo"，你肯定不会从中间翻起，而是直接翻到后面。
插值查找就是基于这个思路。它根据key在数据范围中的比例，估算出可能的位置。公式是：
mid = left + (key - arr[left]) * (right - left) / (arr[right] - arr[left])
说白了，就是按比例插值。如果数据是均匀分布的，插值查找一次就能定位到目标附近，时间复杂度接近O(log log n)，比二分还快。
int interpolation_search(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right && key >= arr[left] && key <= arr[right]) {
if (left == right) {
return (arr[left] == key) ? left : -1;
}
int mid = left + (key - arr[left]) * (right - left) / (arr[right] - arr[left]);
if (arr[mid] == key) return mid;
else if (arr[mid] < key) left = mid + 1;
else right = mid - 1;
}
return -1;
}避坑指南：插值查找对数据分布非常敏感。如果数据分布极不均匀（比如1,2,3,4,5,10000），插值查找可能退化成O(n)，比顺序查找还慢。我曾经在一个温度传感器数据上用过插值查找，结果数据分布是阶梯状的，性能惨不忍睹。后来老老实实换回了二分查找。
斐波那契查找：黄金分割的魅力
斐波那契查找是折半查找的变种。它不取中点，而是用斐波那契数列来分割数组。每次分割点都在黄金分割比例附近（约0.618）。
为什么用斐波那契数列？因为它的分割只涉及加减法，不需要乘除法。在早期的CPU上，乘除法很慢，斐波那契查找就有优势。现在虽然CPU快了，但这个思想依然值得学习。
int fibonacci_search(int arr[], int n, int key) {
int fib2 = 0, fib1 = 1, fib = fib1 + fib2;
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;
}我的看法：斐波那契查找在实际项目中用得不多，因为二分查找已经足够好了。但它的思想很有意思——用加减法代替乘除法。在一些没有硬件乘法器的低端MCU上，这个优势还是存在的。我曾在8位单片机上用过斐波那契查找，确实比二分快那么一点点。
四种查找算法对比
| 算法 | 时间复杂度 | 前提条件 | 适用场景 |
|---|---|---|---|
| 顺序查找（哨兵） | O(n) | 无 | 数据量小，或无序数据 |
| 折半查找 | O(log n) | 有序 | 通用有序查找，最稳定 |
| 插值查找 | O(log log n) ~ O(n) | 有序且均匀分布 | 均匀分布的大数据量 |
| 斐波那契查找 | O(log n) | 有序 | 低算力平台，无乘除法 |
知识体系总览
下面这张图把四种查找算法的关系、适用条件和核心思想都串起来了。你可以把它当作一个快速参考。
看到这张图，你应该能感受到：没有银弹。每种算法都有自己的脾气。顺序查找最简单，什么数据都能用，就是慢。折半查找最均衡，有序数据首选。插值查找在均匀分布时最快，但遇到不均匀数据就翻车。斐波那契查找在低算力平台有优势，但日常开发用得少。
我个人建议：如果你刚开始学，先把顺序查找和折半查找吃透。这两个是基础中的基础。插值查找和斐波那契查找可以作为进阶内容，理解了思想就好，不用死记代码。
好了，查找这块就聊到这儿。记住一点：算法是为实际问题服务的。别为了用算法而用算法，先搞清楚你的数据长什么样，再选最合适的查找方式。