引入

二分查找大家都很熟悉。但二分答案是一个更强大的思想：当答案具有单调性时，可以二分答案的值，然后通过一个判定函数 check 来验证该值是否可行。

具体地，如果问题满足：

  • 答案在一个范围 [l, r] 内。
  • 存在一个阈值 x*，使得 ∀ x ≤ x* 可行，∀ x > x* 不可行（或者反过来）。

那么就可以二分这个阈值。

基本模板

求最大的满足条件的值

“答案越小越容易满足”，即  ≤ x* 可行， > x* 不可行。

1
2
3
4
5
6
7
int l = L, r = R; // 答案范围
while (l + 1 != r) {
  int mid = l + r >> 1;
  if (check(mid)) l = mid;
  else r = mid;
}
// 答案为 l

也可以写成经典的 l <= r 形式，但我个人更喜欢这种写法，不容易写错边界。

求最小的满足条件的值

“答案越大越容易满足”，即  ≥ x* 可行， < x* 不可行。

1
2
3
4
5
6
7
int l = L, r = R;
while (l + 1 != r) {
  int mid = l + r >> 1;
  if (check(mid)) r = mid;
  else l = mid;
}
// 答案为 r

关键点

  • 初始的 l 应设为一个一定不可行的值，r 设为一个一定可行的值（或反过来，取决于单调方向）。
  • check 函数是核心，通常是贪心或模拟。

例题

砍树

例题：洛谷 P1873 [COCI 2011/2012 #5] EKO / 砍树。

题意简述

有 n 棵树，高度分别为 a1, a2, …, an。设定锯子高度 h，所有高于 h 的树都会被锯掉上面的部分。求使得木材总量至少为 m 的最大的 h。

算法分析

h 越大，获得的木材越少。所以”满足木材  ≥ m“这个条件随着 h 增大而越来越难满足。

二分 h，check 中计算 ∑max (ai − h, 0) 是否  ≥ m 即可。

时间复杂度 O(nlog V)，其中 V 为高度的值域。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using lint = long long;

int n;
lint m;
int a[1000010];

bool check(int h) {
  lint sum = 0;
  for (int i = 1; i <= n; ++i)
    if (a[i] > h) sum += a[i] - h;
  return sum >= m;
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  int l = 0, r = *std::max_element(a + 1, a + n + 1) + 1;
  while (l + 1 != r) {
    int mid = l + r >> 1;
    if (check(mid)) l = mid;
    else r = mid;
  }
  std::cout << l << '\n';
  return 0;
}

跳石头

例题：洛谷 P2678 [NOIP2015 提高组] 跳石头。

题意简述

在起点和终点之间有 n 块石头，可以移走其中 m 块，使得相邻两块石头（包括起点和终点）之间的最短跳跃距离最大化。

算法分析

最短距离越小越容易满足（移走更少的石头即可），具有单调性。

二分最短距离 d，check 中贪心地模拟：从左到右扫描，如果当前石头与上一块保留的石头距离  < d，就移走它，统计移走的数量是否  ≤ m。

时间复杂度 O(nlog L)，其中 L 为起点到终点的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

int n, m, L;
int a[50010]; // a[0] = 0, a[n+1] = L

bool check(int d) {
  int cnt = 0, pre = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] - pre < d) ++cnt;
    else pre = a[i];
  }
  return cnt <= m;
}

int main() {
  std::cin.tie(0)->sync_with_stdio(0);
  std::cin >> L >> n >> m;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  a[n + 1] = L;
  int l = 0, r = L + 1;
  while (l + 1 != r) {
    int mid = l + r >> 1;
    if (check(mid)) l = mid;
    else r = mid;
  }
  std::cout << l << '\n';
  return 0;
}

实数二分

有些问题的答案是实数，此时将 while (l + 1 != r) 改为精度控制即可。

1
2
3
4
5
6
double l = L, r = R;
for (int i = 0; i < 100; ++i) { // 迭代固定次数，比 eps 判断更稳定
  double mid = (l + r) / 2;
  if (check(mid)) l = mid;
  else r = mid;
}

迭代 100 次可以将区间缩小 2−100 倍，精度远超 double 的表示范围，足够使用。

相比 while (r - l > eps) 的写法，固定迭代次数不会因为浮点误差导致死循环。

总结

二分答案的核心在于发现单调性。很多”最大化最小值”或”最小化最大值”的问题都可以用二分答案解决。

难点往往不在二分本身，而在于如何设计 check 函数——通常需要贪心或其他算法来验证。