引入：查找是编程中最常见的操作
几乎每一个程序都离不开放东西和找东西：从用户列表里找某个账号、从字典里查一个单词、从日志里定位一条记录。上一篇我们学会了排序，今天就来学习如何利用有序性，把查找速度大幅提升。
查找算法有很多种，我们从最简单的顺序查找开始，再过渡到效率更高的二分查找。
学习目标
- 掌握顺序查找和二分查找的实现。
- 理解二分查找必须满足的前提条件。
- 搞清楚二分查找中
left、right、mid的边界处理。 - 会比较两种查找的时间复杂度和空间复杂度。
顺序查找：逐个比较
思路
顺序查找也叫线性查找，思路最简单：从数组的第一个元素开始，一个一个地和目标值比较，找到了就返回下标，没找到就返回 -1。
它不需要数组有序，对任何数组都适用。
代码实现
#include <stdio.h>
int sequential_search(int a[], int n, int target) {
int i;
for (i = 0; i < n; i++) {
if (a[i] == target) {
return i; // 找到了，返回下标
}
}
return -1; // 没找到
}
int main(void) {
int a[] = {3, 7, 1, 9, 5};
int n = sizeof(a) / sizeof(a[0]);
int target = 9;
int result = sequential_search(a, n, target);
if (result != -1) {
printf("找到 %d，下标为 %d\n", target, result);
} else {
printf("未找到 %d\n", target);
}
return 0;
}
输出：
找到 9，下标为 3
复杂度分析
- 时间复杂度：最好情况下，第一个元素就是要找的，O(1)；最坏情况下要查到最后一个，O(n)；平均也是 O(n)。
- 空间复杂度：只用了几个变量，O(1)。
顺序查找的优点是简单通用，缺点是数据量大时太慢。比如在一百万个元素里找一个数，平均要比较五十万次。
二分查找：每次砍掉一半
思路
如果你要在字典里查一个单词，肯定不会从第一页开始逐页翻，而是先翻到中间，看看目标单词在左半部分还是右半部分，然后再把那一半继续对半分。这种思想就是二分查找。
二分查找有个硬性要求：数组必须是有序的。如果数组无序，就无法判断目标值在哪一半。
二分查找的前提
数组必须按升序或降序排列，且能通过下标 O(1) 访问元素。链表由于无法随机访问，不适合二分查找。
核心思想
维护两个指针 left 和 right，表示当前查找区间。每次取中间位置 mid：
- 如果
a[mid]等于目标值，找到了。 - 如果
a[mid]小于目标值，目标值只可能在右半边，令left = mid + 1。 - 如果
a[mid]大于目标值，目标值只可能在左半边，令right = mid - 1。
重复这个过程，直到找到目标值，或者 left > right 说明不存在。
代码实现
#include <stdio.h>
int binary_search(int a[], int n, int target) {
int left = 0;
int right = n - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2; // 防止 (left + right) 溢出
if (a[mid] == target) {
return mid;
} else if (a[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 没找到
}
int main(void) {
int a[] = {1, 3, 5, 7, 9, 11, 13, 15};
int n = sizeof(a) / sizeof(a[0]);
int target = 7;
int result = binary_search(a, n, target);
if (result != -1) {
printf("找到 %d，下标为 %d\n", target, result);
} else {
printf("未找到 %d\n", target);
}
return 0;
}
输出：
找到 7，下标为 3
二分查找的边界处理
二分查找最容易出错的地方就是边界。很多人的代码会死循环或者漏掉元素，根本原因是没有想清楚“区间是闭区间还是开区间”。
闭区间写法 [left, right]
上面代码用的是闭区间写法：
- 初始：
left = 0, right = n - 1，区间是[0, n-1]，包含两端。 - 循环条件：
left <= right，当两者相等时，区间还有一个元素，仍需检查。 - 移动边界：
left = mid + 1或right = mid - 1，因为mid已经检查过了，新的区间不再包含它。
这是最推荐初学者掌握的写法，逻辑最直观。
为什么 mid = left + (right - left) / 2
你可能会看到有人写成 mid = (left + right) / 2。在大多数情况下没问题，但如果 left 和 right 都是很大的整数，left + right 可能溢出。用 left + (right - left) / 2 可以避免这个问题。
查找第一个/最后一个出现的元素
如果数组中有重复元素，比如 {1, 3, 5, 5, 5, 7, 9}，上面的代码可能返回任意一个 5。如果需要找到第一个或最后一个 5，边界处理会更复杂一些。这属于二分查找的进阶应用，掌握基础版本后可以继续探索。
复杂度分析
时间复杂度
- 顺序查找：O(n)。数据量每翻一倍，平均查找次数也大致翻一倍。
- 二分查找：O(log n)。每次把查找范围减半，所以一百万个元素最多只需要比较约 20 次，因为 2²⁰ ≈ 100万。
这个差距非常惊人。当 n 达到 10⁷ 级别时，顺序查找平均要 500 万次比较，而二分查找最多只需要 24 次左右。
空间复杂度
- 顺序查找：O(1)。
- 二分查找：迭代版本也是 O(1)。如果用递归实现二分查找，递归栈的空间复杂度是 O(log n)。
两种查找的对比
| 特性 | 顺序查找 | 二分查找 |
|---|---|---|
| 前提条件 | 无 | 数组必须有序 |
| 时间复杂度 | O(n) | O(log n) |
| 空间复杂度 | O(1) | O(1)（迭代版） |
| 适用场景 | 数据无序或数据量小 | 数据量大且已排序 |
不要迷信二分查找
如果数据只查一次，或者数组本来就很短，排序再二分查找的总开销可能比直接顺序查找还大。算法的选择要结合实际场景。
常见错误与注意事项
- 忘记数组有序的前提：二分查找只能用于有序数组，如果数组无序，结果不可靠。
- 循环条件写错：闭区间写法用
left <= right，不要写成left < right，否则可能漏掉最后一个元素。 - 边界更新错误：如果写成
left = mid而不是left = mid + 1，可能会导致死循环。 - 忽略整数溢出：写
mid = (left + right) / 2在极端大数据下可能溢出，推荐用left + (right - left) / 2。
二分查找的关键是区间定义
一种稳健写法维护半开区间 [left, right)：
size_t left = 0;
size_t right = length;
while (left < right) {
size_t mid = left + (right - left) / 2;
if (data[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
结束时 left == right，它表示第一个“不小于 target”的位置。若 left < length && data[left] == target，目标存在。
这种写法天然支持查找第一个重复值，也避免 left + right 可能溢出。
二分查找要求的不只是“有序”
更一般地说，需要一个随位置单调变化的真假条件。例如“最小可行容量”“第一个时间戳不早于目标”也能二分。关键是边界一侧都不满足，另一侧都满足。
排序成本也要算进方案
若数据只查一次，先花 O(n log n) 排序再做 O(log n) 查找，可能不如一次 O(n) 顺序查找。若要对同一数据查很多次，排序或建立索引才更可能划算。复杂度分析应覆盖完整工作流。
小结与预告
这一篇我们学习了两种查找方式：
- 顺序查找：简单通用，O(n)，适合无序或小规模数据。
- 二分查找：要求有序数组，每次砍半，O(log n)，适合大规模有序数据。
二分查找的核心在于区间和边界的处理，我推荐你先用闭区间 [left, right] 的版本练熟。
下一篇我会带你进入一个新的思维领域——递归。递归是一种函数调用自身的编程技巧，它能让很多复杂问题变得优雅，但也容易让人头大。我会从函数调用栈的角度帮你彻底理解它。