正式开始之前先讨论一下，二分的本质并非单调性，而是一个区间可以不停地一分为二，使得分开后的左半边满足某种性质而右半边不满足。但最常用的还是单调性的二分。
整数二分
e.g.
红 绿
|____________________||____________________|① 找红色的右端点
mid = (l + r + 1) / 2（防止 l = r – 1 时出问题e.g. l = 6, r = 7, mid == 6 + 7 >> 1 == 6 == l, 进入死循环）,等价于 l + (r – l + 1 >> 1)
if (check(mid)) //满足红色性质
–true: [mid, r]
–flase: [l, mid-1]
② 找绿色的左端点
mid = (l + r) / 2
等价于 l + (r – l >> 1)
if(check(mid)) //满足绿色性质
–true: [1,mid]
–flase: [mid + 1,r]
代码
时间复杂度O(nlogn)
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q; cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 0; i < q; i ++)
{
int k; cin >> k;
int l = 0, r = n - 1;
while (l < r)//找左端点，即从左往右第一个>=k的位置（相当于找绿色（>=k）的左端点）
{
int mid = l + r >> 1;
if (a[mid] >= k) r = mid;
else l = mid + 1;
}
if (a[l] != k) cout << "-1 -1\n";
else
{
cout << l << ' ';
int l = 0, r = n - 1;
while (l < r)//找右端点，即从左往右第一个<=k的位置（相当于找红色（<=k）的右端点）
{
int mid = l + r + 1 >> 1;
if (a[mid] <= k) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}
}
return 0;
}小数二分
小数二分与整数二分相类似，此处以平方根为例。一般保留n位小数，则实际精度控制为1e-(n+2)
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
int main()
{
ld x; cin >> x;
ld l = 0, r = max(x,(ld)1);
while (r - l > 1e-8) //保留n位小数，此处为1e-(n+2)
{
ld mid = (l + r) / 2;
if (mid * mid >= x) r = mid;
else l = mid;
}
cout << l << '\n';
return 0;
}应用
应用广泛，目前不熟悉二分算法，日后补充
2月2日补充
lower_bound和upper_bound的本质都是二分查找。于是就产生了二分会不会被lower_bound取代的疑惑。
经过sunglassman的提醒，二分不一定在数组内二分，而且二分的范围可能很大，超出了评测机内存能接受的内存，比如1e8的范围的二分
2月4日补充
板子一定不要背错，是 while (l < r) 不是 l <= r，如果 l == r 时仍然进入循环就会进入死循环，因为在最后二分的退出条件就是l == r
评论（0）
暂无评论