整数二分

二分步骤

1. 确定check函数
2. 判断check的true和false情况，并更新区间
3. check（m）==true：
   1）l=mid时，mid=（l+r+1）/2
   2）r=mid时，mid=（l+r）/2

二分模板

第一种
当我们将区间 [ l , r ] 划分成 [ l , mid ] 和 [ mid + 1, r ] 时，其更新操作是 r = mid 或者 l = mid + 1 ;计算mid时不需要加1。

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

第二种

当我们将区间 [ l , r ] 划分成 [ l , mid - 1 ] 和 [ mid , r ] 时，其更新操作是 r = mid - 1 或者 l = mid ;此时为了防止死循环，计算 mid 时需要加1。

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

题目

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。

输入格式

第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。

输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。

数据范围

1≤n≤100000
1≤q≤10000
1≤k≤10000

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

代码如下：

#include<iostream>
using namespace std;
const int N=1000010; 
int n,q;
int a[N];

int bsearch1(int x)
{
	int l=0,r=n-1;
	while(l<r){
		int mid=(l+r)/2;
		//a[mid]<=x  相当于check函数，也可以单独写出来
		if(a[mid]>=x) r=mid;
		else l=mid+1;
	}
	//while循环结束是l==r，所以这个地方写成(a[r]==x)也可以
	if(a[l]==x) return l;
	else return -1;
 } 

int bsearch2(int x)
{
	int l=0,r=n-1;
	while(l<r){
		int mid=(l+r+1)/2;
		//同理
		if(a[mid]<=x) l=mid;
		else r=mid-1;
	}
	//同理
	if(a[l]==x) return l;
	else return -1;
}

int main()
{
	cin>>n>>q;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int x;
	while(q--){
		cin>>x;
		cout<<bsearch1(x)<<" ";
		cout<<bsearch2(x)<<endl;
	}
	return 0;
}

浮点数二分

浮点数二分的本质也是边界, 唯一区别是浮点数没有整除, 区间长度可以严格的缩小一半

当区间长度足够小时, 便可以认为是一个数

模板

double bsearch(double l, double r) {
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求, 一般比所求精度高 2
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}