二分

二分算法（binary search）

$\texttt{Although\ the\ basic\ idea\ of\ binary\ search\ is\ comparatively\ straightforward,}$

$\texttt{the\ details\ can\ be\ surprisingly\ tricky.}$

$\tag*{\color{black}\text{——Donald Ervin Knuth}}$

$\texttt\color{white}{the\ details\ can\ be\ surprisingly\ tricky.}$

算法简介

该算法在数学中也有广泛的应用，在数学中，我们求函数零点时也会采取这种方式。

该算法思路非常简单。

二分算法就是当知道答案的范围时，对答案进行夹逼，直到夹逼出答案为止。

具体过程：

1. 已知答案在 $[l,r]$ 的范围内；
2. 每次取 $mid={l+r}\over 2$；
3. 对 $mid$ 进行判定，判断 $mid$ 是否满足条件；
4. 如果 $mid$ 满足条件，缩小区间为 $[mid,r]$，否则缩小区间为 $[l,mid]$；
5. 回到 2 操作继续进行，直到找到答案或精度足够为止。

要求

在进行二分查找时，必须保证序列有序，或者对于任一条件 $cmp()$，长度为 $n$ 的数组 $a$ 中恰有一点 $i$，使得 $[1,i]$ 都满足 cmp 函数，使得 $[i+1,n]$ 都不满足 $cmp()$ 函数。

求函数零点时，必须保证在所求范围内，函数单调（不一定需要严格单调）。

分类

★ 整数二分

整数二分时，我们的退出条件应为 l>r 或 l>=r（因写法而异），而缩小区间时，我们需要使得 l=mid+1 或 r=mid-1 或同时进行（同样也因写法而异）。

证书二分通常用于下列情况：求大于（等于）或小于（等于）一个数字的第一个（最后一个）数字、求整数答案、求整数（自然数）最优解。

★ 小数（浮点数）二分

小数二分时，我们的退出条件应为 r-l<eps（其中 $eps$ 表示需要的精度，因题目要求而异，通常设置为题目要求的精度乘以 $10^{-2}$），而缩小区间时，我们需要使得 l=mid 或 r=mid。

小数二分通常用于下列情况：求函数零点、求浮点数答案、求方程的解、求平均值或距离等可能出现小数的答案。

时间复杂度是一个典型的 $O(\log n)$，常数也很小，效率非常高。

代码

整数二分

例题：https://www.luogu.com.cn/problem/P2249。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6+3;

int a[N];

int bsearch(int n,int lim) { //二分
	int lef=1,rig=lim; //设置答案区间 [lef,rig]
	while(lef<=rig) { //循环查找
		int mid=(lef+rig)>>1; //取区间中值 mid
		if(a[mid]>=n) rig=mid-1; 
		else lef=mid+1; //判断情况，对答案区间进行更新
	} //直到答案区间锁定时退出循环
	return lef; //一定要注意最后返回的是 lef 还是 rig
}

int main() {
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>a[i];
	while(q--) {
		int tt;
		cin>>tt;
		int id=bsearch(tt,n);
		cout<<((a[id]==tt)?id:-1)<<' ';
        //在本题中，我们二分查找的是第一个大于等于 tt 的元素 a[id] 
        //如果这个元素 a[id] 不等于 tt，那么数组中找不到 tt。
        //证明简单，从略。
	}
	return 0;
}

小数（浮点数）二分

这里以求二次方根这个十分简单的题目为例。

#include <bits/stdc++.h>

using namespace std;

const double eps=1e-6;
const int inf=1<<30;

double bsqrt(int n) {
	double l=0,r=inf;
	while(r-l>eps) {
		double mid=(l+r)/2;
		if(mid*mid>n) r=mid;
		else l=mid;
	}
	return l;
}

int main() {
	int q;
	cin>>q;
	while(q--) {
		int n; cin>>n;
		cout<<fixed<<setprecision(6)<<bsqrt(n)<<'\n';
	}
  return 0;
}

洛谷练习题单：https://www.luogu.com.cn/training/111#problems