二分

问你啥，你就二分啥 ~

二分查找

二分查找的前提是一个顺序表，即一张有序（升序或降序）的表。

例1

在一组升序的数组中 ，查找值为 的数组下标，若找不到，则输出“Can’t find”。

解1

这题十分常规，核心代码如下：

l = 1, r = n;
while(l < r){
    mid = (l + r) / 2;
    if(a[mid] == x) {cout << mid << endl; return;}
    if(a[mid] < x) l = mid + 1;
    else r = mid - 1;
}
cout << "Can't find" << endl; return;

例2

在一组升序的数组中 ，查找值为 的数组下标，若找不到，则输出比 小的最大值的下标。

解2

这道题和例1的区别就是，当找不到时，需要返回比 小的最大值的下标，核心代码如下：

l = 1, r = n;
while(l < r){
    mid = (l + r + 1) / 2;
    if(a[mid] <= x) l = mid;
    else r = mid - 1;
}
cout << l << endl; return;

mid = (l + r + 1) / 2 是因为，如果 mid = (l + r) / 2 ，当 l = 1, r = 2 且 a[1] <= x 时，将会陷入死循环。所以在书写代码时，我们可以适当检验，来决定 mid 的取值。

二分答案

典型的使用场景: 要求我们求出某种条件的最大值的最小可能情况或者最小值的最大情况

使用前提:

1. 答案在一个固定的区间内
2. 难以通过搜索来找到符合要求的值, 但给定一个值你可以很快的判断它是不是符合要求
3. 可行解对于区间要符合单调性, 因为有序才能二分嘛

要想利用二分答案我们需要找到单调性，如图所示

例1

https://www.luogu.com.cn/problem/P2678

解1-1

最怕写什么 dfs\bfs 结果Co老师让我先不管复杂度，dfs 一下，我真是太难了。枚举拿走的 块石头。，代表石头，伪代码如下：

vector<int> S; // 存放拿走的石头
dfs(int x, int y){ //x为a的下标，y为当前向量中的元素个数
    if(x == n + 1 || y == m) {give(S); return;}
    S.push_bach(a[x]); //a[x]放进去
    dfs(x + 1, y + 1); 
    S.pop_back();
    dfs(x + 1, y); //a[x] 不放进去
}
int main(){
    dfs(1,0);
}

解1-2

对于这道题来说，我们令横坐标 的含义为，拿走石头以后，每一步的距离都大于等于 ，即最短路径大于等于 ，而判断是否成立的条件就是，拿走石头的数量是否小于等于 。

在 很小的时候一定成立，在 很大的时候一定不成立。

#include <bits/stdc++.h>
#define N 50008
using namespace std;

int a[N];
int m, n, l;

inline bool valid(int x){
	int nowl = 0, cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(a[i] - nowl < x) ++cnt;
		else nowl = a[i];
	}
	return cnt <= m;
}

int main(){
	cin >> l >> n >> m;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	int le = 0, re = l;
	while(le < re){
		int mid = (le + re + 1) / 2;
		if(valid(mid)) le = mid;
		else re = mid - 1;
	}
	cout << le << endl;
	return 0;
}

例2

https://www.acwing.com/problem/content/141/

解2

根据上一篇博客的内容，我们知道，要判断两个串是否相等，可以采用哈希的方式。因为要判断的是回文串，所以我们需要计算正反两种哈希值。

在这里我们可以发现，对于一个固定的中间位置（可能是一个字符，可能是空），长度大的时候成立，则长度小的时候一定成立，长度很小的时候（为0）一定成立，所以长度就是我们要找的单调性，即要二分的 。

#include <bits/stdc++.h>
#include <algorithm>
#define N 1000007
#define base 31
#define mod 100000007
using namespace std;

char s[N];
int h[N], h1[N], B[N], Max, cnt;


inline int hhr(int l, int r) {
    return (h[r] - 1ll * h[l - 1] * B[r - l + 1] % mod + mod) % mod;
}

inline int hhl(int l, int r) {
    return (h1[l] - 1ll * h1[r + 1] * B[r - l + 1] % mod + mod) % mod;
}

inline bool valid(int pos, int len){
	return hhl(pos - len, pos - 1) == hhr(pos + 1, pos + len);
}

inline bool valid1(int pos, int len){
	return hhl(pos - len + 1, pos) == hhr(pos + 1, pos + len);
}

inline void cB(){
	B[0] = 1;
	for (int i = 1; i <= N; ++i)
        B[i] = 1ll * B[i - 1] * base % mod;
}

int main() {
	cB();
	while(scanf("%s", s + 1)){
		Max = 0;
		if(s[1] == 'E') return 0;
		else{
			int len = strlen(s + 1);
			
    		for (int i = 1; i <= len; ++i)
        		h[i] = (1ll * h[i - 1] * base + s[i] - 'a') % mod;
        		
        	h1[len + 1] = 0;
    		for (int i = len; i; --i)
        		h1[i] = (1ll * h1[i + 1] * base + s[i] - 'a') % mod;
        		
        	for(int i = 1; i <= len; ++i){
        		
        		int ll = 0; int rr = min(i - 1, len - i);
        		while(ll < rr){
        			int mid = (ll + rr + 1) / 2;
        			if(valid(i, mid)) ll = mid;
        			else rr = mid - 1;
				}
				Max = max(Max, 2 * ll + 1);
				ll = 0; rr = min(i, len - i);
        		while(ll < rr){
        			int mid = (ll + rr + 1) / 2;
        			if(valid1(i, mid)) ll = mid;
        			else rr = mid - 1;
				}
				Max = max(Max, 2 * ll);
			}
		}
		printf("Case %d: %d\n", ++cnt, Max);
	}
}

例3

实数域：https://www.luogu.com.cn/problem/P1577

解3

#include <bits/stdc++.h>
#define N 10008
using namespace std;

double a[N];
int n, k;

inline bool valid(double x){
	int cnt = 0;
	for(int i = 1; i <= n; ++i){
		cnt += a[i] / x;
	}
	return cnt >= k;
}

int main(){
	cin >> n >> k;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
	}
	double le = 0.0, re = 100007.3;
	while(le + 0.01 < re){
		double mid = (le + re) / 2.0;
		if(valid(mid)) le = mid;
		else re = mid;
	}
	cout << le << endl;
	return 0;
}

例4

https://www.luogu.com.cn/problem/P1182

解4

#include <bits/stdc++.h>
#define N 100005
using namespace std;

int a[N], n, m;

inline bool work(int x){ //每段的长度都小于等于x
	int cnt = 0, sum = 0;
	for(int i = 1; i <= n; ++i){
		sum = a[i];
		while(i < n && sum + a[i + 1] <= x) {
			i++;
			sum += a[i];
		}
		cnt++;
	}
	return cnt <= m;
}

int main(){
	cin >> n >> m;
	int i = 0, j = 0;
	for(int k = 1; k <= n; ++k){
		cin >> a[k];
		if(a[k] > i) i = a[k];
		j += a[k];
	}
	while(i < j){
		int mid = (i + j)/2;
		if(work(mid)) j = mid;
		else i = mid + 1;;
	}
	cout << j;
	return 0;
}