23. 查找算法：顺序查找、有序表查找
查找，说白了就是在一堆数据里找到你想要的那个。我做了这么多年嵌入式开发，几乎每个项目都离不开查找操作。从最简单的传感器数据检索，到复杂的路由表匹配，查找算法的选择直接影响系统响应速度。
今天咱们就把三种最基础的查找算法掰开揉碎讲清楚。顺序查找、折半查找、插值查找、斐波那契查找——嗯，一个一个来。
23.1 顺序查找：最朴素的暴力法
顺序查找的思路简单到令人发指：从第一个元素开始，挨个比较，直到找到目标或者遍历完整个数组。
我曾经在一个数据采集项目中用过这个算法。当时数据量不大，也就几百个采样点，用顺序查找完全够用。但后来数据量涨到几万，系统就开始卡顿了——这就是没提前评估复杂度的教训。
代码实现
// 顺序查找：返回目标索引，未找到返回 -1
int seqSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}复杂度分析
| 情况 | 比较次数 | 时间复杂度 |
|---|---|---|
| 最好情况 | 1（第一个就是） | O(1) |
| 最坏情况 | n（最后一个或不存在） | O(n) |
| 平均情况 | (n+1)/2 | O(n) |
核心结论：顺序查找的时间复杂度是 O(n)。数据量小的时候无所谓，数据量一大就扛不住了。
小技巧：我习惯在数组末尾加一个"哨兵"（把目标值放在 arr[n] 位置），这样就不用每次循环都判断下标是否越界。实测能省掉大约 15% 的比较开销。
23.2 折半查找：有序数据的利器
折半查找，也叫二分查找。前提条件很明确：数据必须有序。你想想看，如果数据是乱序的，折半查找就没法用。
我记得有一次接手一个老项目，里面用的就是顺序查找，数据量大概 10 万条。我改成折半查找后，查找时间从秒级降到了毫秒级。老板当时还问我是不是换了服务器——其实只是换了个算法。
代码实现
// 折半查找：数组必须有序（升序）
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}注意：计算 mid 时不要写成 (left + right) / 2。当 left 和 right 都接近 INT_MAX 时，相加会溢出。用 left + (right - left) / 2 更安全——这是我在一次代码审查中学到的。
复杂度分析
折半查找每次把查找范围缩小一半。所以查找次数就是 log₂(n) 级别。具体来说：
- 最好情况：O(1) —— 中间元素就是目标
- 最坏情况：O(log n) —— 一直找到最底层
- 平均情况：O(log n)
说白了，10 亿条数据用折半查找，最多只需要比较 30 次。而顺序查找可能要比较 10 亿次。差距就是这么大。
23.3 插值查找：更聪明的折半
折半查找每次都在中间切一刀。但你想过没有——如果数据分布比较均匀，我们其实可以猜得更准。
比如你要在一本 1000 页的字典里找"苹果"这个词。你不会从第 500 页开始翻，而是会从前面几页开始。插值查找就是这个思路。
核心公式
插值查找的 mid 计算公式变成了：
mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left])这个公式说白了就是：根据目标值在数据范围内的"比例位置"来猜测索引。如果数据分布均匀，这个猜测非常准。
代码实现
// 插值查找：适用于数据分布均匀的有序数组
int interpolationSearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right && target >= arr[left] && target <= arr[right]) {
// 防止除零
if (arr[left] == arr[right]) {
if (arr[left] == target) return left;
else return -1;
}
int mid = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left]);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}复杂度对比：
- 数据均匀分布时：O(log log n) —— 比折半查找还快
- 数据分布极不均匀时：O(n) —— 退化成顺序查找
我个人建议：只有在数据量较大且分布比较均匀的情况下才用插值查找。否则折半查找更稳定。
23.4 斐波那契查找：黄金分割的妙用
斐波那契查找，名字听着挺唬人。其实它和折半查找很像，只是分割点不是中间，而是黄金分割点附近。
为什么会用斐波那契数列？因为斐波那契数列相邻两项的比值趋近于黄金分割比 0.618。用这个比例来分割数组，在某些场景下可以减少磁盘 I/O 次数——我记得在数据库索引设计中有人研究过这个。
核心思想
先构造一个斐波那契数列 F[k]，使得 F[k] 刚好大于等于数组长度 n。然后每次用 F[k-1] 作为分割点。
// 斐波那契查找
int fibSearch(int arr[], int n, int target) {
// 构造斐波那契数列，F[k] >= n
int fib[100];
fib[0] = 0; fib[1] = 1;
int k = 1;
while (fib[k] < n) {
k++;
fib[k] = fib[k-1] + fib[k-2];
}
// 扩展数组到 fib[k] 长度
int* temp = (int*)malloc(fib[k] * sizeof(int));
memcpy(temp, arr, n * sizeof(int));
for (int i = n; i < fib[k]; i++) {
temp[i] = arr[n-1]; // 用最后一个元素填充
}
int left = 0, right = fib[k] - 1;
while (left <= right) {
int mid = left + fib[k-1] - 1;
if (temp[mid] == target) {
free(temp);
return (mid < n) ? mid : n-1;
} else if (temp[mid] < target) {
left = mid + 1;
k -= 2; // 右边部分长度是 F[k-2]
} else {
right = mid - 1;
k -= 1; // 左边部分长度是 F[k-1]
}
}
free(temp);
return -1;
}实际经验：斐波那契查找在实际工程中用得不多。我做了这么多年项目，只用过一次——在一个对内存访问模式有特殊要求的嵌入式系统里。大多数情况下，折半查找已经够用了。
23.5 四种查找算法对比总结
| 算法 | 前提条件 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 顺序查找 | 无 | O(n) | O(1) | 小数据量、无序数据 |
| 折半查找 | 有序 | O(log n) | O(1) | 通用有序查找 |
| 插值查找 | 有序且均匀分布 | O(log log n) ~ O(n) | O(1) | 均匀分布的大数据量 |
| 斐波那契查找 | 有序 | O(log n) | O(1) | 特殊内存访问场景 |
23.6 知识体系结构图
下面这张图帮你理清四种查找算法的关系与选择逻辑：
23.7 避坑指南
最后分享几个我踩过的坑：
- 我曾经在一个项目中直接用折半查找，结果数据是降序排列的——找了半天找不到。记住：折半查找的前提是数组有序，而且你得知道是升序还是降序。
- 我曾经在插值查找里没处理除零问题，arr[right] - arr[left] 等于 0 时直接崩溃。现在我的代码里都会加这个判断。
- 我建议初学者先从顺序查找入手，理解透了再学折半查找。别一上来就搞斐波那契查找——那个在实际项目中真的很少用。
查找算法是数据结构的基础，也是面试的高频考点。把这四种算法吃透，你就能应对绝大多数查找场景了。