二分法

前言

二分思想可以理解成是对枚举的一种优化，假设一个问题的解分布在01区间里，而这种解与某种递增变量有联系。那么，我们可以通过枚举这个变量来得到正解。暴力枚举的方法效率较低，而二分查找优化了这一枚举过程。

• 二分题目的关键词：最xx的最xx，比如：最大的最近距离是多少?

整数二分模板

//关于模板的一些说明：
//对于数组 arr[10] = {1,4,5,6,6,6,7,8,9,10};
//若要找到同样满足check的情况下，下标较大者，应该以l为答案
//此时查找区间为[l,r-1]
int main(void){
	int l = 0;
	int r = 10;
	int x = 6;
	while(l+1 != r){
		int mid = (l+r)/2;
		if(arr[mid] <= x) l = mid;
		else r = mid;
	}
	cout<<l; //5
}
//若要找到同样满足check的情况下，下标较小者，应该以r为答案
//此时查找区间为[l+1,r]
int main(void){
	int l = -1;
	int r = 9;
	int x = 6;
	while(l+1 != r){
		int mid = (l+r)/2;
		if(arr[mid] >= x) r = mid;
		else l = mid;
	}
	cout<<r; //3
}

浮点二分模板

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-6; //设置精度

double f(const double &x){
	return x*x + 2*x -1;
}

int main(void){
	// f = x^2 + 2x -1;
	// 求f(x) = m 的 x 的值
	double l = 0;
	double r = 1e10;
	double m;cin>>m;
	while(r-l >= eps){
		double mid = (r+l)/2;
		if(f(mid) > m){
			r = mid;
		}
		else l = mid;
	}
	cout<<r; //输出l或者r可以，没有太大区别
	return 0;
}

例题1：跳石头

1.跳石头 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6;

ll len,n,m;
ll rock_pos[MAX];

bool check(const int & x){
	ll last_pos = 0;
	ll ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(rock_pos[i] - last_pos < x){
			ans++;
			continue;
		}
		last_pos = rock_pos[i];
	}
	if(len - last_pos < x) ans++;
	return ans >= m;
}

int main(void){
	cin>>len>>n>>m;
	for(int i = 1 ; i <= n ; i ++){
		cin>>rock_pos[i];
	}
	ll l = 0;
	ll r = 1e9 + 5;
	while(l+1 != r){
		ll mid = (l+r)/2;
		if(check(mid)){
			r = mid;
		}
		else l = mid;	
	}
	cout<<r;
	return 0;
}

例题2：肖恩的苹果林

1.肖恩的苹果林 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6;

ll n,m;
ll tree_pos[MAX];

ll check(const int & x){
	ll ans = 1;
	ll last = tree_pos[1];
	for(int i = 2 ; i <= n ; i ++){
		if(tree_pos[i] - last >= x){
			ans++;
			last = tree_pos[i];
		}
	}
	return ans;
}

int main(void){
	cin>>n>>m;
	for(int i = 1 ; i <= n ; i++){
		cin>>tree_pos[i];
	}
	sort(tree_pos+1,tree_pos+1+n);
	ll l = 0;
	ll r = 1e9+10;
	while(l+1 != r){
		ll mid = (l+r)/2;
		if(check(mid) >= m){
			l = mid;
		}
		else r = mid;	
	}
	cout<<l;
	return 0;
}