二分与三分
2025/9/13约 718 字大约 2 分钟
二分与三分
二分查找、由二分法衍生的三分法以及二分答案
二分查找
在一个有序数组中查找某一元素的算法。
手写
写法一
int n, m, a[1000005];
void solve(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
// 遍历q 查询
for (int i = 1; i <= m; i++) {
int q;
cin >> q;
// 二分查找
int l = 1, r = n;
while (l < r)
{
int mid = l + ((r - l) >> 2); // 左中位数
// int mid = l + (r - l + 1) / 2; // 右中位数
if (a[mid] >= q) r = mid; // 相同的值取下标最小的
else l = mid + 1;
}
// 结束时 l = r
if (a[l]==q) cout << l << " ";
else cout << -1 << " ";
}
}写法二
int a[1000005];
int binary_search(int l, int r, int q) {
int ret = -1; // 未搜索到数据返回-1下标
while (l <= r) {
int mid = l + ((r - l) >> 2); // 使用与方法一相同的中位数计算方式
if (a[mid] < q)
l = mid + 1;
else if (a[mid] > q)
r = mid - 1;
else { // 找到目标值时记录位置并退出
ret = mid;
break;
}
}
return ret; // 单一出口
}STL 的二分查找
- 查找首个不小于给定值的元素的函数
std::lower_bound - 查找首个大于给定值的元素的函数
std::upper_bound - 返回值为指针，减数组首地址得到下标。
void solve2(){
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
// 遍历q
for (int i = 1; i <= m; i++) {
int q;
cin >> q;
// lower_bound返回的是指针，减去a的地址得到下标
int ans = lower_bound(a + 1, a + n + 1, q) - a;
// 判断是否存在
if (ans > n || a[ans] != q) cout << -1 << " ";
else cout << ans << " ";
}
}最大值最小化
要求满足某种条件的最大值的最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的「最大值」，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快地找到答案。因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：
- 答案在一个固定区间内；
- 可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
- 可行解对于区间满足一定的单调性。
当然，最小值最大化是同理的。
题目链接
二分答案
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。