二分查找 & 二分答案详解

好文推荐：here

二分模板

尽量往左找目标

while(l<r){
    int mid=(l+r)>>1;
    if(check(mid))
        r=mid;
    else
        l=mid+1;
}

尽量往右找目标

while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid))
        l=mid;
    else
        r=mid-1;
}

二分答案套路

最大值最小

check 函数里的判断为 。

最小值最大

check 函数里的判断为 。

二分常用函数

• lower_bound : 在有序的序列中查找第一个不小于 value 的位置
• upper_bound : 在有序的序列中查找第一个大于 value 的位置

例题

P2249:

Sol

二分查找。题目要求的是尽量往左找目标。我这里使用了 lower_bound 函数。

Code

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	while(m--){
		int x;
		cin>>x;
		int ans=lower_bound(a+1,a+n+1,x)-a;
		if(x!=a[ans])
			cout<<-1<<' ';
		else
			cout<<ans<<' ';
	}
	return 0;
}

P1102:

Sol

我们遍历数组，让每一个值先变成B，然后二分找对应的 A 首次出现位置。我原本用 map 写的，就不贴代码了。

P1182:

Sol

直接二分答案。check 函数直接扫一遍数组只要 sum 大于 mid 就分新的一段即可。

Code

#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long arr[100005],sum[100005];
bool check(long long res){
	int now=0;
	int cnt=0;
	for(int i=2;i<=n;i++){
		if(sum[i]-sum[now]>res){
			cnt++;
			now=i-1;
		}
	}
	if(cnt>=m)
		return true;
	return false;
}
int main(){
    cin>>n>>m;
    cin>>arr[1];
    sum[1]=arr[1];
    long long r,l=-1;
	for(int i=2;i<=n;i++){
		cin>>arr[i];
		sum[i]=arr[i]+sum[i-1];
		l=max(l,arr[i]);
	}
	r=sum[n];
	while(l<=r){
		long long mid=(l+r)/2;
		if(check(mid))
			l=mid+1;
		else
			r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

友情提醒：不要无脑 Ctrl C+Ctrl V