二分查找

读完能做什么

• 能在一段已经有序的数据里，用 binary_search 判断某个值在不在。
• 能用 lower_bound 找出“第一个不小于 x 的位置”，用 upper_bound 找出“第一个大于 x 的位置”。
• 能用 upper_bound - lower_bound 算出 x 出现了几次，并说出这两个边界为什么相减。
• 能看懂查询值不存在、数据全部相等、区间为空这三种情况下两个边界落在哪里。

为什么需要它

find 要从头到尾一个个看，数据有 n 个就得比较 n 次。但如果数据已经排好序，可以更聪明地找：每次都看中间那个元素，比目标小就往右半段找，比目标大就往左半段找，一次砍掉一半。这样最多比较大约 log2(n) 次，n 是 100 万时也只要 20 次左右。

“砍一半”这个动作也有一套固定写法，标准库把它做成了几个函数：判断存在用 binary_search，找边界位置用 lower_bound 和 upper_bound。它们比 find 快得多，但代价是要求数据已经有序——前提不满足时结果不可靠。

它是什么

一句话：二分查找族在一段按同一规则有序的区间里，用“每次砍掉一半”的方式回答问题。

先分清三个函数各自回答什么：

几个必须就地看懂的概念：

“不小于”就是“大于或等于”。 lower_bound 找第一个满足“元素 >= x”的位置。如果 x 存在，它就是第一个 x 的位置。

“大于”是严格大于。 upper_bound 找第一个满足“元素 > x”的位置，也就是第一个 x 之后的位置。

位置与下标。 这三个函数返回的是迭代器。lo - v.begin() 把位置换算成下标，要求迭代器能相减（vector、deque、数组可以；list、set 不行）。

必须有序，且查询与排序用同一条规则。 默认用 < 比较，所以数据要从小到大排好。如果你用 greater<int>() 把数据排成降序，查询时也必须传同一个 greater<int>()，否则“砍一半”的方向就反了。

返回 end() 时不能取值。 所有元素都比 x 小时，lower_bound、upper_bound 都会返回区间的终点 last。这个位置指向的不是任何元素，只能拿来比较，不能解引用。

使用时要 #include <algorithm>，本页示例用 #include <bits/stdc++.h> 一次包含全部标准头文件。

最小可运行示例

数据 [1, 2, 2, 2, 5] 已经从小到大排好，查 2：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 2, 5};      // 已经按从小到大排好

    cout << "存在 2 吗：" << binary_search(v.begin(), v.end(), 2) << '\n';

    auto lo = lower_bound(v.begin(), v.end(), 2);   // 第一个不小于 2 的位置
    auto hi = upper_bound(v.begin(), v.end(), 2);   // 第一个大于 2 的位置

    cout << "下界下标：" << (lo - v.begin()) << '\n';
    cout << "上界下标：" << (hi - v.begin()) << '\n';
    cout << "2 出现次数：" << (hi - lo) << '\n';
    return 0;
}

输出：

存在 2 吗：1
下界下标：1
上界下标：4
2 出现次数：3

逐行看：

• binary_search(v.begin(), v.end(), 2) 返回 true，打印成 1（bool 输出默认是 0/1）。
• lower_bound 返回第一个不小于 2 的位置。下标 0 的 1 小于 2，下标 1 的 2 不小于 2，所以下界停在下标 1。
• upper_bound 返回第一个大于 2 的位置。下标 1、2、3 都是 2，下标 4 的 5 才是第一个大于 2 的，所以上界停在下标 4。
• hi - lo 是两个位置相减，得到中间夹着几个位置：4 - 1 = 3，正好是 2 出现的次数。

一步步看变化

还是这组数据，把两个边界标在同一行上：

下界停在下标 1，上界停在下标 4，中间 [下界, 上界) 覆盖下标 1、2、3 这三个 2。所以：

graph LR
    p0["下标 0 值 1"] --> p1["下标 1 值 2"]
    p1 --> p2["下标 2 值 2"]
    p2 --> p3["下标 3 值 2"]
    p3 --> p4["下标 4 值 5"]
    L["下界 停在下标 1"] -.-> p1
    U["上界 停在下标 4"] -.-> p4

再用同一个数据查三个不同的值，看边界怎么动：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 2, 5};
    vector<int> queries = {3, 6, 1};

    for (int x : queries) {
        auto lo = lower_bound(v.begin(), v.end(), x);
        auto hi = upper_bound(v.begin(), v.end(), x);
        cout << "查 " << x
             << "：存在吗 " << binary_search(v.begin(), v.end(), x)
             << "，下界 " << (lo - v.begin())
             << "，上界 " << (hi - v.begin())
             << "，次数 " << (hi - lo) << '\n';
    }
    return 0;
}

输出：

查 3：存在吗 0，下界 4，上界 4，次数 0
查 6：存在吗 0，下界 5，上界 5，次数 0
查 1：存在吗 1，下界 0，上界 1，次数 1

• 查 3：数据里没有 3。第一个不小于 3 的是下标 4 的 5，第一个大于 3 的也是下标 4 的 5，两个边界重合，次数是 0。
• 查 6：所有元素都小于 6，两个边界都跑到尾后位置，下标都是 5。这就是返回 end() 的情况，只能比较，不能取值。
• 查 1：下标 0 的 1 就是它，下界停在下标 0；下标 1 的 2 是第一个大于 1 的，上界停在下标 1，次数是 1。

规律：查一个不存在的值时，下界和上界会重合（都停在“它本该插入的位置”），相减得 0。

逐项扩展核心操作

binary_search 返回的是真假，不是位置

binary_search 只回答“在不在”，它不告诉你“在第几个”。所以不能拿它的返回值当下标用：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 2, 5};

    bool found = binary_search(v.begin(), v.end(), 2);
    cout << "存在 2 吗：" << found << '\n';

    // 想知道"第一个 2 在哪"，要另外用 lower_bound
    auto lo = lower_bound(v.begin(), v.end(), 2);
    cout << "第一个 2 的下标：" << (lo - v.begin()) << '\n';
    return 0;
}

输出：

存在 2 吗：1
第一个 2 的下标：1

bool found = ... 接住的是一个真假值。想要位置就必须换 lower_bound。判断存在也可以用 lower_bound：lower_bound(...) 得到的下界如果指向一个值恰好等于 x，就说明存在，但更直接的写法是用 binary_search。

数据全部相等

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {7, 7, 7, 7};      // 全部相等

    auto lo = lower_bound(v.begin(), v.end(), 7);
    auto hi = upper_bound(v.begin(), v.end(), 7);
    cout << "下界 " << (lo - v.begin()) << "，上界 " << (hi - v.begin())
         << "，次数 " << (hi - lo) << '\n';
    return 0;
}

输出：

下界 0，上界 4，次数 4

所有元素都是 7：下界停在第一个位置（下标 0），上界跑到尾后位置（下标 4），次数是 4，正好是元素个数。

空区间

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v;                     // 空区间

    auto lo = lower_bound(v.begin(), v.end(), 5);
    auto hi = upper_bound(v.begin(), v.end(), 5);
    cout << "存在吗：" << binary_search(v.begin(), v.end(), 5) << '\n';
    cout << "下界就是 end() 吗：" << (lo == v.end()) << '\n';
    cout << "下界与上界相等吗：" << (lo == hi) << '\n';
    return 0;
}

输出：

存在吗：0
下界就是 end() 吗：1
下界与上界相等吗：1

空区间里没有任何元素，两个边界都落在 end() 上，binary_search 返回假，次数是 0。

按自定义规则查询：数据怎么排，就怎么查

如果数据是用 greater<int>() 从大到小排的，查询也必须传同一条规则：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {5, 2, 2, 2, 1};   // 已经按从大到小排好

    // 查询也必须用同一条比较规则 greater<int>()
    auto lo = lower_bound(v.begin(), v.end(), 2, greater<int>());
    auto hi = upper_bound(v.begin(), v.end(), 2, greater<int>());

    cout << "下界下标：" << (lo - v.begin()) << '\n';
    cout << "上界下标：" << (hi - v.begin()) << '\n';
    cout << "2 出现次数：" << (hi - lo) << '\n';
    return 0;
}

输出：

下界下标：1
上界下标：4
2 出现次数：3

在降序数据里，“第一个不小于 2”理解为“第一个不大于 2 的位置”（因为大的在前面），“第一个大于 2”理解为“第一个小于 2 的位置”。规则换了，含义跟着换，但 upper - lower 仍然是出现次数。关键是一致：排序用哪条规则，查询就用哪条规则。

什么时候选它、哪里容易错

前提是数据已经有序。 二分查找每次都要“看中间、砍一半”，数据没序就砍错了地方，结果没有意义：

// 错误示例：数据没有排序就用二分查找，结果不可靠
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 2};            // 没有排序

    cout << binary_search(v.begin(), v.end(), 2) << '\n';   // 结果不可靠，不要照着写
    return 0;
}

这段能编译，但打印出来的真假没有意义。要先用 sort 排好，再查。

排序规则和查询规则要一致。 用 sort(v.begin(), v.end(), greater<int>()) 排成降序，却用默认的 < 去 lower_bound，方向就反了：

// 错误示例：数据按从大到小排序，却用默认的 < 规则去查，边界没有意义
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {5, 2, 2, 2, 1};         // 降序

    auto lo = lower_bound(v.begin(), v.end(), 2);   // 缺了 greater<int>()，规则不一致
    cout << (lo - v.begin()) << '\n';               // 打印出来的下标不可信
    return 0;
}

这段能编译，打印出来也有数字，但那个下标没有意义：数据是按从大到小排的，查询却按默认的 < 规则找，方向对不上，结果取决于具体实现。排序规则和查询规则必须成对出现（要么两边都用 greater<int>()，要么两边都用默认的 <，写成 lower_bound(v.begin(), v.end(), 2, greater<int>())）。

binary_search 返回 bool，不能当位置。 要位置就得用 lower_bound / upper_bound。

返回 end() 时不能取值。 查一个比所有元素都大的值时，两个边界都跑到 end()，*lo 是越界访问，结果不确定。用之前先和 v.end() 比较。

算下标要求迭代器能相减。 lo - v.begin() 在 vector、deque、数组上可以；list、set 上不行，得改用 distance(lo, v.begin())（选读，代价是逐个走）。

泛型算法和容器的成员查询不是一回事。 set、map 也有 find、lower_bound、upper_bound 成员函数。它们不是“从头走到位置”，而是沿着树一层层比较下去，所以访问元素本身就要 O(log n) 次，而泛型 lower_bound 在 vector 上是“每次随机跳到中间”，跳转是 O(1) 的。两者复杂度都写成 O(log n)，但常数和适用场景不同：数据是静态、要按位置随机访问就用 vector + 泛型算法；要边插入边查询就用 set / map 的成员版本。set / map 见 set 有序集合。

复杂度。 binary_search、lower_bound、upper_bound 的比较次数都是 O(log n)，与迭代器种类无关；但在 list 这类不能随机跳的容器上，走到中间要一步步移动，定位的代价加起来是 O(n)，所以这族函数在 vector 上才划算。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），数据已经有序。请先手推出输出，再运行核对：

vector<int> v = {1, 2, 2, 2, 5};
auto lo = lower_bound(v.begin(), v.end(), 5);
auto hi = upper_bound(v.begin(), v.end(), 5);
cout << (lo - v.begin()) << ' ' << (hi - v.begin()) << '\n';

第 2 题：修改代码

下面这段片段读入一组已经排好序的数和一个目标值，请补上计算“目标值出现次数”的语句，让输出是出现次数：

int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
int x;
cin >> x;

// 在这里补上计算 x 出现次数的语句，并输出

用这组输入核对：第一行 5，第二行 1 2 2 2 5，第三行 2，输出应该是 3。

验证条件：先说出 lower_bound 和 upper_bound 分别停在下标几，再运行核对。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 2, 2, 5};
    auto lo = lower_bound(v.begin(), v.end(), 5);
    auto hi = upper_bound(v.begin(), v.end(), 5);
    cout << (lo - v.begin()) << ' ' << (hi - v.begin()) << '\n';
    return 0;
}

4 5

#include <bits/stdc++.h>
using namespace std;

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

    auto lo = lower_bound(v.begin(), v.end(), x);
    auto hi = upper_bound(v.begin(), v.end(), x);
    cout << (hi - lo) << '\n';
    return 0;
}

5
1 2 2 2 5
2

3

立即练习

两道题都只需要数组、循环、排序和本页的二分查找函数。做完后请说明：第一题为什么不能直接用 binary_search？