二分查找
给定一个从小到大排序的数组,求第一个大于等于
如果是直接找,单次查找的时间复杂度是
明显这样太花费时间了,而且可以优化:
比如说,你一开始就直接看第三个位置,发现第三个位置上的数字小于
那么我们不妨直接去看中间位置:
如果中间位置小于
如果中间位置大于等于
这样,整个需要查找的区间就减小了一半!
这样查找下去,只要找
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]>=k) r=mid-1;
else l=mid+1;
}
cout<<r+1<<'\n';//用'\n'换行会比endl快好多。
2
3
4
5
6
7
8
我们把这个问题抽象一下:
把从小到大排序的数组
对于一次查询,求第一个大于等于
我们要求的位置,其实就是在求满足
我们先规定一个一开始的求解范围
每次去询问中间位置的值
发现在
所以,只要是单调函数求零点的问题,都可以二分。
二分答案
求
但我们仔细想,如果设这样一个函数:
这种问题答案具有单调性,题目给出的
例题:
有
我们可以直接二分这个
我们也可以映射到函数去:
int check(int x)
{
int sum=0;
for(int i=1;i<=n;++i) sum+=max(0,h[i]-x);
return sum;
}
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)>=m) l=mid+1;
else r=mid-1;
}
cout<<l-1<<'\n';
2
3
4
5
6
7
8
9
10
11
12
13
14
15
另一类经典问题:
有一个长度为
比如数列[4,2,4,5,1]要分成三段。
分法一:[4,2],[2,5],[1],每一段的和分别是
分法二:[4],[2,4],[5,1],每一段的和分别是
最大值最小是
对于这种最大值最小/最小值最大一类的问法,通常也是二分答案
这样设置函数:
也就可以二分答案了。
int check(int x)
{
int sum=0,cnt=1;
for(int i=1;i<=n;++i)
{
if(sum+a[i]<=x) sum+=a[i];
else
{
++cnt;
sum=x;
}
}
return cnt;
}
int l=maxn,r=1e9;//这个问题中,l必须等于所有a[i]的最大值。
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid)<=m) r=mid-1;
else l=mid+1;
}
cout<<l-1<<'\n';
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
二分答案可以看作是:对于那些答案有单调性的求值问题,我们花费了
STL
对于二分查找,可以使用
int a[101];//a是一个从小到大排好序,范围是a[1]~a[n]的数组。
int p1=lower_bound(a+1,a+n+1,x)-a;//p1是二分找到的第一个大于等于x的位置。
int p2=upper_bound(a+1,a+n+1,x)-a;//p2是二分找到的第一个大于x的位置。
2
3