往期浏览

讲解与模板

整数域二分算法

\(\mathcal O(\log N)\) 的复杂度使得其应用极为广泛，除了手写二分函数外，还有一些库函数可以使用：

lower_bound(x)：返回大于等于 \(x\) 的第一个迭代器；
upper_bound(x)：返回大于 \(x\) 的第一个迭代器；
binary_search(x)：在容器中二分查找 \(x\) 是否存在。

我的模板参考自Acwing，分为两个部分：

在递增序列 \(a\) 中查找 \(\geq x\) 数中最小的一个（即 \(x\) 或 \(x\) 的后继）：

while (l < r) {
  int mid = (l + r) / 2;
  if (a[mid] >= x) r = mid;
  else l = mid + 1;
}
return a[l];

在递增序列 \(a\) 中查找 \(\leq x\) 数中最大的一个（即 \(x\) 或 \(x\) 的前驱）：

while (l < r) {
  int mid = (l + r + 1) / 2;
  if (a[mid] <= x) l = mid;
  else r = mid - 1;
}
return a[l];

实数域二分算法

引入了实数后需要考虑精度问题，目前主流的写法是限制二分次数，当然也可以使用浮点数比较法，这里两种都列出。

for (int t = 1; t <= 100; t++) {
    long double mid = (l + r) / 2;
    if (judge(mid)) r = mid;
    else l = mid;
}
cout << l << endl;

while (r - l > EPS) {
    long double mid = (l + r) / 2;
    if (judge(mid)) r = mid;
    else l = mid;
}
cout << l << endl;

整数域三分算法

三分的一大运用便是求解函数的极值点，虽然很高大上但是实际写起来并不复杂，基本与二分一致。

while (l < r) {
    int mid = (l + r) / 2;
    if (check(mid) <= check(mid + 1)) r = mid;
    else l = mid + 1;
}
cout << check(l) << endl;

实数域三分算法

这类题目我接触的非常少，暂时留个坑。

while (r - l > EPS) {
    long double mid = (l + r) / 2;
    l = mid - EPS;
    r = mid + EPS;
    if (judge(l) < judge(r)) r = mid;
    else l = mid;
}
cout << l << endl;

题单与部分题解

AcWing 789. 数的范围：整数域二分

题意：给出一个递增序列，然后有 \(Q\) 次询问，每个询问包含一个数字 \(x_i\) ，对于每个询问，输出 \(x_i\) 在序列中第一次出现的下标和最后一次出现的下标。

思路：建立模型，第一次出现的下标即为查找左边界的位置；最后一次出现的下标则同理。

P2678 [NOIP2015 提高组] 跳石头：整数域二分

题意：河上有一些石头，选手需要跳石头过河。现在，至多可以移走 \(K\) 块石头，请你输出最短跳跃距离的最大值。

思路：显然，移走越多的石头，答案一定越大。二分“跳跃距离”，找到符合条件（至多移走 \(K\) 块石头）的最大跳跃距离。建立模型，即为查找右边界。满足 l = mid 条件的情况是“跳跃距离小”，而跳跃距离越小移走的石头数量越少，所以满足该条件的情况是 judge[mid] <= K 。

P1182 数列分段 Section II：整数域二分

题意：有一个由正整数构成的序列，现在，你需要将这个序列划分为 \(K\) 段，使得每段和的最大值最小。

思路：二分“每段和的最大值”，找到符合条件（恰好划分成 \(K\) 段）的最小值。建立模型，即为查找左边界。注意，满足 r = mid 条件的情况是“和大”，而和越大段数越少，所以满足该条件的情况是 judge[mid] <= K 。

P1824 进击的奶牛：整数域二分

题意：有 \(N\) 个牛棚，已知每个牛棚的位置，现在需要将 \(M\) 头牛安置进去，请你给出一个最佳方案，使得牛们彼此的最近距离最大，直接输出这个值。

思路：二分“距离”，找到符合条件（ \(M\) 头牛）的最大值。建立模型，即为查找右边界。注意，满足 l = mid 条件的情况是“距离小”，而牛越多距离越小，所以满足该条件的情况是 judge[mid] >= M 。

P7585 [COCI2012-2013#1] LJUBOMORA：整数域二分

题意：有 \(M\) 种颜色不同数量不同的弹珠要分给 \(N\) 个孩子，每个孩子得到的弹珠颜色必须相同，输出分到弹珠最多的孩子的最小值。

思路：二分“分到的弹珠数量”，找到符合条件（恰好分给 \(N\) 个孩子）的最小值。建立模型，即为查找左边界。注意，满足 r = mid 条件的情况是“分到的弹珠数量多”，而分到的越多分给的人数越少，所以满足该条件的情况是 judge[mid] <= N 。

P3853 [TJOI2007]路标设置：整数域二分

题意：路上有一系列路标，现在至多可以增设 \(K\) 个路标，使得相邻路标的最大距离最小，输出这个距离。

思路：显然，增设的路标越多，最大距离的最小值越小。二分“距离”，找到符合条件（至多增设 \(K\) 个路标）的最小值。建立模型，即为查找左边界。注意，满足 r = mid 的条件的情况是”距离大“，而距离越大增设的路标数量越少，所以满足该条件的情况是 judge[mid] <= K 。