11. 数组查找算法：线性查找与二分查找
查找，说白了就是在数据堆里找到你想要的那个值。我做了这么多年嵌入式开发，几乎每个项目都离不开查找操作——从传感器数据里找异常值，从配置表里找匹配项，从日志里找关键信息。今天咱们就聊聊两种最基础的查找算法：线性查找和二分查找。
11.1 线性查找：最朴素的思路
线性查找的思路简单到令人发指：从头到尾，一个一个比。找到了就返回位置，找不到就返回-1。我刚开始学C语言时，第一个自己写出来的查找函数就是线性查找。
核心思想：遍历数组，逐个比较，直到找到目标值。
// 线性查找：在数组 arr 中查找 key
// 找到返回下标，找不到返回 -1
int linear_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // 找到了，返回下标
}
}
return -1; // 没找到
}这段代码，嗯，没什么好解释的。就是循环加判断。但你别小看它，我在实际项目中还真遇到过用它解决问题的场景——有一次处理一个实时数据流，数据量不大（几十个），但数据是动态变化的，没法排序。这时候二分查找用不了，线性查找反而是唯一的选择。
适用场景：
- 数组无序时
- 数据量很小（比如几十个元素）
- 只需要查找一次，不值得排序
线性查找的时间复杂度是 O(n)。最坏情况下，你要找的值在最后一个位置，或者根本不存在，那就得把整个数组翻个底朝天。
11.2 二分查找：效率的飞跃
二分查找就不一样了。它要求数组必须是有序的，然后每次把查找范围砍掉一半。我当年第一次看到这个算法时，心里想的是：「还能这么玩？」
核心思想：每次取中间元素比较，如果比目标大，就去左半边找；如果比目标小，就去右半边找。每次缩小一半范围。
// 二分查找：在有序数组 arr 中查找 key
// 找到返回下标，找不到返回 -1
int binary_search(int arr[], int n, int key) {
int left = 0;
int 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 都很大，加起来可能溢出。用减法就安全多了。
避坑指南：
- 数组必须有序！我曾经在项目里忘了排序就直接调二分查找，结果查了半天查不到，排查了半小时才发现问题。
- 边界条件要小心：left <= right 还是 left < right？我建议用 left <= right，逻辑更清晰。
- mid 的计算要防溢出，用减法形式。
二分查找的时间复杂度是 O(log n)。你想想看，1000个元素的数组，线性查找最坏要比较1000次，二分查找最多10次。差距就是这么明显。
11.3 两种算法的对比
| 对比项 | 线性查找 | 二分查找 |
|---|---|---|
| 前提条件 | 无序/有序均可 | 必须有序 |
| 时间复杂度 | O(n) | O(log n) |
| 空间复杂度 | O(1) | O(1) |
| 适用场景 | 小数据量、无序数据 | 大数据量、有序数据 |
| 代码复杂度 | 简单 | 稍复杂（注意边界） |
11.4 手写二分查找的要点
面试时经常让手写二分查找。我面过不少人，能一次写对的不多。常见的坑有这些：
- 循环条件写错：写成 left < right，结果最后一个元素永远查不到。
- mid 更新不对：找到 mid 后，left 或 right 直接等于 mid，导致死循环。
- 没考虑重复元素：如果数组里有重复值，二分查找返回的是哪个位置？不一定是最左边或最右边的。
我个人习惯在写二分查找时，先画个简单的数组在纸上，手动模拟一遍。比如数组 [1, 3, 5, 7, 9]，查找 7。走一遍流程，边界条件就清楚了。
11.5 二分查找的变体
实际项目中，我们经常需要查找第一个等于目标值的位置，或者最后一个等于目标值的位置。这时候标准二分查找就不够用了。
// 查找第一个等于 key 的位置
int binary_search_first(int arr[], int n, int key) {
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
result = mid; // 记录当前位置
right = mid - 1; // 继续往左找
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
// 查找最后一个等于 key 的位置
int binary_search_last(int arr[], int n, int key) {
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
result = mid; // 记录当前位置
left = mid + 1; // 继续往右找
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}这两种变体在实际中很常用。比如你有一个学生成绩表，想找到所有考了90分的学生，用 binary_search_first 找到第一个90分的位置，再用 binary_search_last 找到最后一个，中间这一段就是所有90分的学生。
11.6 知识体系图
下面这张图帮你理清本章的核心逻辑：
11.7 我的建议
如果你刚开始学，我建议你先吃透线性查找。它简单，不容易出错。等你能闭着眼睛写出线性查找了，再挑战二分查找。
二分查找的难点不在算法本身，而在边界条件的处理。我见过太多人在 left <= right 和 left < right 之间纠结。我的建议是：统一用 left <= right，配合 left = mid + 1 和 right = mid - 1，这个组合最不容易出错。
最后说一句：别觉得这些基础算法简单就轻视它。我在实际项目中，二分查找的 bug 修复率比复杂算法高得多。越是基础的东西，越要写扎实。
公众号：蓝海资料掘金营，微信 deep3321