二分查找与二分答案

吴老师

2026-10-15 20:12:31

发布于：广东

11阅读

0回复

0点赞

二分查找与二分答案

一、认识时间复杂度

写程序时，我们不仅要考虑结果是否正确，还要考虑程序运行得够不够快。

时间复杂度就是用来描述：随着数据量变大，算法需要执行的操作次数会怎样增长。

假设有 n 个数：

时间复杂度	通俗理解
O(1)	操作次数基本不变
O(log n)	每次排除一大半数据
O(n)	把 n 个数看一遍
O(n log n)	常见高效排序算法的复杂度
O(n²)	两层循环，每层最多执行 n 次

例如，在 100 万个数中寻找一个数：

顺序查找： 从头到尾逐个比较，最坏需要比较 100 万次，时间复杂度为 O(n)。
二分查找： 每次排除一半不可能的数，最多只需要约 20 次比较，时间复杂度为 O(log n)。

这就是为什么我们需要学习二分查找。

二、二分查找

例题 1：U119411.【模板】二分查找

如果数组没有顺序，要寻找某个数，通常只能逐个检查。

但如果数组已经从小到大排好序，就可以利用大小关系，快速缩小查找范围。

例如，在下面的数组中寻找 15：

2 5 8 12 15 19 23

首先检查中间的 12。

因为 15 比 12 大，所以 12 及其左边的数都不可能是答案，只需要继续寻找右半部分：

15 19 23

再检查中间的 19。

因为 15 比 19 小，所以继续寻找左半部分：

15

成功找到目标。

原本可能要逐个检查 7 个数，现在只检查了 3 次。

二分查找的核心思想：每次检查中间位置，根据比较结果，排除一半不可能的答案。

如何实现？

使用三个变量：

l：当前查找范围的左端点。
r：当前查找范围的右端点。
mid：当前查找范围的中间位置。

初始时，l = 1，r = n。

只要 l <= r，就不断重复以下操作：

计算中间位置：mid = l + (r - l) / 2。
如果 a[mid] == x，说明找到了。
如果 a[mid] > x，说明目标只可能在左半部分，令 r = mid - 1。
如果 a[mid] < x，说明目标只可能在右半部分，令 l = mid + 1。

如果一直没有找到，直到 l > r，说明数组中不存在目标。

核心代码

bool found = false;
int l = 1, r = n;

while (l <= r) {
    int mid = l + (r - l) / 2;

    if (a[mid] == x) {
        found = true;
        break;
    }
    else if (a[mid] > x) {
        r = mid - 1;
    }
    else {
        l = mid + 1;
    }
}

if (found) cout << "YES\n";
else cout << "NO\n";

二分查找的时间复杂度为 O(log n)。

注意：二分查找要求数组有序。如果原数组无序，需要先排序，排序的时间复杂度通常为 O(n log n)。

三、STL 中的二分查找

普通二分只能判断某个数是否存在。有时候，我们还想知道某个数应该出现在哪个位置。

C++ 为我们提供了两个常用函数：

lower_bound：寻找第一个大于等于 x 的位置。
upper_bound：寻找第一个严格大于 x 的位置。

它们都要求查找范围已经按升序排列，时间复杂度都是 O(log n)。

例题 2：A8020.第一个大于等于 x 的数

考虑下面的升序数组（下标从 1 开始）：

下标	1	2	3	4	5	6	7
数值	3	8	8	8	8	15	23

如果查找第一个大于等于 8 的位置，答案为 2。

使用 lower_bound：

int pos = lower_bound(a + 1, a + n + 1, x) - a;

这里：

a + 1：查找范围的起点。
a + n + 1：查找范围终点的下一个位置。
- a：将找到的位置转换成数组下标。

如果不存在大于等于 x 的元素，返回 n + 1。

例题 3：A8021.第一个大于 x 的数

仍然使用上面的数组。

如果查找第一个严格大于 8 的位置，答案为 6。

使用 upper_bound：

int pos = upper_bound(a + 1, a + n + 1, x) - a;

同样，如果不存在符合条件的元素，返回 n + 1。

两个函数的区别

函数	查找条件	x = 8 时的结果
`lower_bound`	第一个 ≥ x	2
`upper_bound`	第一个 > x	6

记住：

lower 可以等于，upper 必须大于。

四、二分查找的综合应用

例题 4：A23650.数字出现的次数

已经学会寻找某个数的左右边界，就可以进一步利用二分查找统计数字出现的次数。

首先，将整数转换为字符串。因为我们只关心数字，所以负数需要去掉负号。

然后，对字符串进行排序，让相同数字排列在一起。

例如：

212533

排序后变成：

1 2 2 3 3 5

观察数字 3：

lower_bound 找到第一个 3 的位置。
upper_bound 找到最后一个 3 后面的第一个位置。

因此：

某个数字出现的次数 = upper_bound 的位置 − lower_bound 的位置。

核心代码

string s;
cin >> s;

if (s[0] == '-') s = s.substr(1);

sort(s.begin(), s.end());

for (char ch = '0'; ch <= '9'; ch++) {
    int l = lower_bound(s.begin(), s.end(), ch) - s.begin();
    int r = upper_bound(s.begin(), s.end(), ch) - s.begin();

    cout << r - l << '\n';
}

这道题说明，二分查找不仅可以用来寻找某个数，还能通过寻找边界，解决统计问题。

五、二分答案

前面学到的二分查找，都是在一个有序数组中寻找某个位置。

但二分还有一种非常重要的用法：二分答案。

它不是直接计算最优答案，而是先猜测一个答案，再判断这个答案能否实现。

如果能够根据判断结果排除一半候选答案，就可以使用二分。

例题 5：A29698.木材加工

我们希望得到尽可能长的木材，但是木材越长，能够切出来的段数就越少。

因此，可以先猜测一个长度 x，再判断这个长度能不能满足要求。

第一步：设计 check 函数

对于一根长度为 a[i] 的木材，如果每段长度为 x，就能切出 a[i] / x 段。

把所有木材能够切出的段数加起来：

如果总段数 ≥ k，说明这个长度可行。
如果总段数 < k，说明这个长度不可行。

bool check(long long x) {
    long long tot = 0;

    for (int i = 1; i <= n; i++) {
        tot += a[i] / x;
        if (tot >= k) return true;
    }

    return false;
}

第二步：寻找答案的单调性

假设长度为 10 时，可以切出足够多的木材。

那么长度为 9、8、7……时，也一定能切出足够多的木材。

反过来，如果长度为 10 时，无法切出足够多的木材，那么长度为 11、12、13……时，也一定不行。

因此，所有候选长度可以分成两个连续的部分：

可行可行可行可行 | 不可行不可行不可行

而我们希望寻找的是：

最后一个可行的答案，也就是最大的可行长度。

第三步：二分寻找最大可行值

初始时：

l = 1，最小候选长度。
r = 最大原木长度，最大候选长度。
ans = 0，记录目前找到的最大可行答案。

每次取中间长度 mid：

如果 check(mid) 为真，说明当前长度可行，记录答案 ans = mid，然后令 l = mid + 1，尝试更长的木材。
如果 check(mid) 为假，说明当前长度不可行，令 r = mid - 1，尝试更短的木材。

完整代码

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

const int N = 1e5 + 5;
long long a[N], n, k;

bool check(long long x) {
    long long tot = 0;

    for (int i = 1; i <= n; i++) {
        tot += a[i] / x;
        if (tot >= k) return true;
    }

    return false;
}

int main() {
    cin >> n >> k;

    long long l = 1, r = 0, ans = 0;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        r = max(r, a[i]);
    }

    while (l <= r) {
        long long mid = l + (r - l) / 2;

        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}