中 · 查找

二分查找

一百万个有序的数,二十次就能找到。二分查找是整个题库里性价比最高的算法 —— 也是最容易被写出细微错误的那个。

一句话答案维护 lo 和 hi，每次用 mid = (lo + hi) / 2 折半，返回 0 基下标或者 -1 —— 数组保证有序，所以 O(log n) 可以替代线性扫描。

题目

输入: 第一行一个整数 n(1 ≤ n ≤ 10000)。第二行 n 个严格递增的整数,空格隔开。第三行是要找的值 x。

输出: x 的下标(从 0 开始);如果不存在,输出 -1。

样例:

输入	输出
`5 1 3 5 8 9 8`	`3`
`5 1 3 5 8 9 7`	`-1`
`1 42 42`	`0`

从 0 循环到 n−1 也能得到正确答案 —— 但它最多要看 10000 个数,而二分只要看大约 14 个。测试数据很小,真正重要的是习惯。

你的解答

main.cpp — 你的解答

「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 想一个 1 到 100 之间的数

你猜 50,我说「大了」,你立刻知道答案不在 1–50 里。一个问题就删掉了一半可能性。整个算法就是这个 —— 计算机唯一多做的事,是用下标精确地执行它。

提示 2 — 两个指针相向收缩

用 lo 和 hi 表示「还可能包含 x」的闭区间。看 mid = (lo + hi) / 2。若 a[mid] 偏小,它左边的一切也都偏小,所以 lo = mid + 1;若偏大,hi = mid - 1;相等就结束了。

提示 3 — 难的是循环条件

用 while (lo <= hi),不要用 lo < hi。写成 < 时,「只剩一个元素」的区间永远不会被检查 —— 于是 n = 1 永远输出 −1,哪怕那个数就在那儿。另外千万别写 hi = mid:配合 lo <= hi 会死循环。

题解（先自己试试！）

#include <iostream>
using namespace std;

int a[10005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int x;
    cin >> x;

    int lo = 0, hi = n - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

搜一万个数要 14 次比较,搜一百万个要 20 次。这就是 O(log n) 买到的东西,而它成立的前提是数据有序 —— 有序性是一种信息,二分查找就是花掉它的方式。真实用途:C++ 标准库里的 lower_bound 就是它,它也是数据库索引的内核。最后一道最大子段和问的是另一个问题:不是「它在哪」,而是「哪一段最好」。

深度解析

为什么这样做对

猜 50,被告知「大了」,一半可能性就没了。二分只是把这个动作精确到下标上。

代价

O(log n):一万个数 14 次比较,一百万个 20 次。线性扫描要一百万次 —— 差五万倍。

常见错法

循环条件写成 while (lo < hi),区间里只剩一个元素时它永远不会被检查,于是 n = 1 永远输出 −1。
写 hi = mid 而不是 hi = mid - 1,配合 lo <= hi 会死循环 —— 直接把标签页卡死。

下一步

最后一题换个问法:不问「它在哪」,问「哪一段最好」—— 最大子段和。

记住这两句

有序性是一种信息,二分就是花掉它的方式。
思路不难,难的是 lo <= hi 和 mid ± 1 这几个边界。

🐞 这段是错的 —— 点开,亲手让它挂一次

lo < hi 让「只剩一个元素」的区间永远不被检查,n = 1 时永远输出 −1

#include <iostream>
using namespace std;

int a[10005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int x;
    cin >> x;

    int lo = 0, hi = n - 1, ans = -1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}