基础算法：二分

🪁简介

二分查找（binary search），也称折半搜索、对数搜索是用来在一个有序数组中查找某一元素的算法。

🪁时间复杂度

二分查找的最优时间复杂度为O(1) 。

二分查找的平均时间复杂度和最坏时间复杂度均为 O(logn)。

🪁空间复杂度

迭代版本的二分查找的空间复杂度为O(1) 。

递归（无尾调用消除）版本的二分查找的空间复杂度为O(logn) 。

🪁详讲

就好比说你要从一本英汉词典上查一个单词，你从头到尾一页一页的翻着找，这样找可以保证一定能找到，但是最坏情况你要把整本词典都翻一遍，那就麻烦了。

有什么改进的方法吗？当然有。

考虑把这个词典从中间分开，看一下中间那一页的主要单词都是啥，然后去判断我要找的单词应该在左半部分还是右半部分，再去那一部分考虑怎么找就好了。同样的，在另一部分也是要进行划分并且判断的操作。这样一直进行下去，便能很快的找到答案，而且根本不需要翻过整个词典来。

可以证明，如果一页一页的找，最多要找n次，但是用这个方法，最多找floor(log2n)次。

我们把这个方法叫做“二分答案”。顾名思义，它用二分的方法枚举答案，并且枚举时判断这个答案是否可行。但是，二分并不是在所有情况下都是可用的，使用二分需要满足两个条件。一个是有界，一个是单调。

二分答案应该是在一个单调闭区间上进行的。也就是说，二分答案最后得到的答案应该是一个确定值，而不是像搜索那样会出现多解。二分一般用来解决最优解问题。刚才我们说单调性，那么这个单调性应该体现在哪里呢？

可以这样想，在一个区间上，有很多数，这些数可能是我们这些问题的解，换句话说，这里有很多不合法的解，也有很多合法的解。我们只考虑合法解，并称之为可行解。考虑所有可行解，我们肯定是要从这些可行解中找到一个最好的作为我们的答案， 这个答案我们称之为最优解。

最优解一定可行，但可行解不一定最优。我们假设整个序列具有单调性，且一个数x为可行解，那么一般的，所有的x’(x’<x)都是可行解。并且，如果有一个数y是非法解，那么一般的，所有的y’(y’>y)都是非法解。

那么什么时候适用二分答案呢？如果题目规定了有“最大值最小”或者“最小值最大”的东西，那么这个东西应该就满足二分答案的有界性（显然）和单调性（能看出来）。

可以使用一个check函数判断这个解是不是可行解。如果这个解是可行解，那么有可能会有比这更优的解，那么我们就去它的左边或者右边二分。（比如在一个递增区间上求“最小值最大”问题，显然再右边的值肯定比左边大，那么我们就有可能找到比这更优的解，直到找不到，那么最后找到的解就有理由认为是区间内最优解。反过来，如果二分到的这个解是一个非法解，我们就不可能再去右边找了。因为性质，右边的解一定全都是非法解。那么我们就应该去左边找解。整个过程看起来很像递归，实际上，这个过程可以递归写， 也可以写成非递归形式。）

🪁整数二分模板

在写整数二分时，可以分为两种情况，一种将数轴分为[L,mid],[mid+1,R]两个部分，另一种将数轴分为[L,mid-1],[mid,R]两个部分，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool check(mid){//判断条件函数 
}


//终止条件是left==right 
//第一种 将区间分为[L,mid],[mid+1,R]
while(left<right){
	int mid=(left+right)>>1;//这里使用右移运算主要是在负数时右移向下取整，除法向零取整
	if(check(mid)) right=mid;//判断如果mid这个值满足[L,mid]这个区间里面的的数的性质，则将r=mid，缩小范围 
	else left=mid+1; //否则另l=mid+1，+1的原因是mid不满足条件不能取 
}
cout<<left;//循环结束后 此时left=right=mid


//第二种 将区间分为[L,mid-1],[mid,R]
while(left<right){
	int mid=(left+right+1)>>1;// +1的主要原因是如果r-l=1，因为>>1是向下取整，所以mid=l，如果很不幸if(check()) left=mid;成立的话，会陷入死循环。 
	if(check(mid)) left=mid;//判断如果mid这个值满足[mid,R]这个区间里面的的数的性质，则将l=mid，缩小范围 
	else right=mid-1; //否则另r=mid-1，-1的原因是mid不满足条件不能取 
}
cout<<left;

总结：该模板保证最终答案处于闭区间[l,r]以内，循环以l=r结束，每次二分的中间值mid会归属于左半段与右半段二者之一，优点是几乎可以用于所有的二分题型，但缺点是需要分清楚两种情况，并根据实际情况选择相应的模板。

🪁实数二分模板

相比较整数上的二分，实数域上的二分就简单很多了，实数域上二分需要注意的点是确定精度，这里有一个小技巧，如果题目上让保留k位小数，那么精度eps就设置成1e^(-k-2)

1
2
3
4
5
6
7
8
9
//这里只是举例 具体情况具体分析
double l=0,r=1000;//这里l与r的值一定要根据题目来设定，不能想当然的就从0开始
while(r-l>eps){
	double mid=(r-l)/2;
	if(check()) l=mid;
	else r=mid;
} 
cout<<l;

有的时候精度难以控制，也可以用设立二分次数的方法来控制精度,例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
//具体情况具体分析
#include<iostream>
using namespace std;
int main(){
	double l=0,r=1000;
	for(int i=0;i<100;i++){
		double mid=(l+r)/2;
		if(check()) l=mid;
		else r=mid;
	}
	
	printf("%lf",l);
}

🪁一道二分题目

🚀传送点: 1227. 分巧克力

题目描述

儿童节那天有 K 位小朋友到小明家做客。

小明拿出了珍藏的巧克力招待小朋友们。

小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。

切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。

当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含两个整数 Hi 和 Wi。

输入保证每位小朋友至少能获得一块 1×1 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

数据范围

1≤N,K≤105,
1≤Hi,Wi≤105

样例

输入样例：
1
2
3
2 10
6 5
5 6
输出样例：
1
2

思路

小巧克力边长 x 一定在 1 – 100000 之间,要在大巧克力中划分出的小巧克力块数 >=k

所以在 1 – 100000 之间找到一个最大的数，使得所有的 (w[i]/x) * (h[i]/x) 之和大于要求的数量 k

使用二分法找到x的最大取值即为答案。

C++ 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//二分法 用第二个模板
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],w[N];//数组 储存巧克力的长宽
int n,k;
//二分的判断条件
bool check(int x){
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=(h[i]/x)*(w[i]/x);//分到巧克力的数量，不是面积的简单分割 (h[i]/x)*(w[i]/x) 每个巧克力长宽允许切割几行几列，再相乘得到矩阵
		if(sum>=k)return true; //大于等于人数时满足条件 返回true
	}
	return  false;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++)cin>>h[i]>>w[i];
	int l=0,r=1e5;//最大数值为100000，作为二分区间
	while(l<r){
		int mid=l+r+1>>1;//l=mid 需要+1防止陷入死循环
		if(check(mid))l=mid;//左边是满足check的全部值，依次增大，找到左边最大的值
		else r=mid-1;
	}
	cout<<l<<endl;
	return 0;
}

其他二分题目: