二分¶
前置知识¶
排序，单调性，分治思想
目标¶
二分查找（背模板）
二分答案（理解check函数）
STL 用法
What¶
二分查找算法（binary search algorithm）
是一种在有序数组中查找某一特定元素的搜索算法。
使用二分的前提条件是，必须在单调有序的数组上进行，或者可以局部舍弃
每一次比较，都使搜索范围缩小一半。
最坏情况下，需要进行O(logn)次比较。
最直接的例子是，猜数字游戏。猜小了，往大里猜；猜大了，往小里猜。
整数二分¶
模板01¶
// 有序数组，找数字 k 第一次出现的位置(保证有答案)
int l = 0, r = n - 1, best = -1;
while (l <= r){
int mid = (l + r) >> 1;
if (a[mid] >= k) r = mid - 1, best = mid;
else l = mid + 1;
}
cout << best;
// 有序数组，找数字 k 最后一次出现的位置(保证有答案)
int l = 0, r = n - 1, best = -1;
while (l <= r){
int mid = (l + r) >> 1;
if (a[mid] <= k) l = mid + 1, best = mid;
else r = mid - 1;
}
cout << best;
模板02¶
// 有序数组，找数字 k 第一次出现的位置(保证有答案)
int l = 0, r = n - 1;
while (l < r){
int mid = (l + r) >> 1;
if (a[mid] >= k) r = mid;
else l = mid + 1;
}
cout << l;
// 有序数组，找数字 k 最后一次出现的位置(保证有答案)
int l = 0, r = n - 1, best = -1;
while (l < r){
int mid = (l + r + 1) >> 1;
if (a[mid] <= k) l = mid;
else r = mid - 1;
}
cout << l;
例题，【深基13.例1】查找 - 洛谷¶
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, m;
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
while (m--)
{
int x;
scanf("%d", &x);
int l = 1, r = n, best = -1;
while (l <= r)
{
int mid = (l + r) / 2;
if (a[mid] >= x) r = mid - 1, best = mid;
else l = mid + 1;
}
if (best == -1 || a[best] != x) cout << -1 << ' ';
else cout << best << ' ';
}
puts("");
return 0;
}
STL¶
一般的数值查找，我们可以直接使用 STL
但如果是二分答案，我们则必须手写 check 函数
// 常见的场景，找大于x的第一个数，找小于x的最后一个数
// lower_bound() ，在指定区域内查找 大于等于 目标值的第一个元素
// upper_bound() ，在指定区域内查找 严格大于 目标值的第一个元素
int pos = lower_bound(a, a + n, x) - a;
int pos = upper_bound(a, a + n, x) - a;
浮点数二分¶
前面讲的二分，是整数值域上的二分。
如果遇到小数的问题，我们要使用下面的模板。
模板03¶
int T = 100;
while (T--)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
例题，给定一个浮点数n，求它的三次方根¶
#include <iostream>
using namespace std;
int main()
{
double x;
scanf("%lf", &x);
bool fushu = false;
if (x < 0) fushu = true, x = -x;
int T = 100;
double l = 0, r = 10000;
while (T--)
{
double mid = (l + r) / 2;
if (mid * mid * mid >= x) r = mid;
else l = mid;
}
if (fushu) printf("-%lf", l);
else printf("%lf", l);
return 0;
}
例题，【深基13.例1】查找 - 洛谷¶
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (m--)
{
int x;
scanf("%d", &x);
int pos = lower_bound(a, a + n, x) - a;
if (a[pos] != x) printf("-1 ");
else printf("%d ", pos + 1);
}
puts("");
return 0;
}
二分答案¶
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。
把这里的枚举换成二分，直接减半运算，就变成了「二分答案」。
猜这个答案是否成立，是一个很有用的优化途径。
能否二分，有一个界定标准：状态的决策过程或者序列是否满足单调性或者可以局部舍弃
例题，1247：河中跳房子¶
题意：从 0 跳到 L，中间有一些石头。最多可移走 m 个石头的情况下，最长的最短跳跃距离是多少
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int q[N];
int L, n, m;
bool check(int dist)
{
int last = 0, cnt = 0;
for (int i = 1; i <= n + 1; i++){
if (q[i] - last < dist) cnt++; //小于最短跳跃距离，此点移除
else last = q[i];
}
// 移除石头的个数，小于等于m
// 跳跃距离，可以再长一点
// 长了，就可以移除更多的石头
// 返回true，可以跳的更长一点
return cnt <= m;
}
int main()
{
cin >> L >> n >> m;
for (int i = 1; i <= n; i++) cin >> q[i];
q[0] = 0, q[n + 1] = L;
int l = 0, r = 1e9+10, ans = -1;
while (l <= r){
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans << '\n';
return 0;
}
例题，1242：网线主管¶
题意：有 n 个长短不一的网线，现在要剪出来 k 条长短一样的网线，希望这 k 条网线越长越好。问最长的长度
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const double eps = 1e-6;
double a[N];
int n, k;
bool check(double x)
{
int cnt = 0;
for (int i = 0; i < n; i++)
cnt += (int)(a[i] / x);
if (cnt >= k) return true;
else return false;
}
int main()
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
double l = 0.0, r = 2e9;
int n = 100;
while (n--){
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
int res = (int)(r * 100);
if (res == 0) printf("0.00\n");
else printf("%.2lf\n", 1.0 * res / 100); // 这道题目输出格式有亿点坑
return 0;
}
P1083 [NOIP2012 提高组] 借教室¶
在这个题里，因为如果前一份订单都不满足，那么之后的所有订单都不用继续考虑；而如果后一份订单都满足，那么之前的所有订单一定都可以满足，符合局部舍弃性，所以可以二分订单数量。
题单¶
总结¶
只有20%的程序员，可以写好二分？
这个看起来不难，写起来却一坨 shit。
我想你很快会有这种体验。
参考¶
https://www.luogu.com.cn/article/sncheqxz
更新记录¶
2025/4/15，更新模板，更新例题