二分模板一共有两个，分别适用于不同情况。

算法思路：

假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

版本1

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

C++ 代码模板：

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;
}

版本2

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

C++ 代码模板：

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;
}

举例：

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

int a[] = {0,1,2,3,3,3,5,5,6,7} ;

int l = 0, r = 9;
//找 第一个大于等于3的位置 
int find(int x){
    while(l < r){
        int mid = (l+r) /2;
        if(a[mid] >= x) r = mid;
        else l = mid+1;
    }
    return l;
} 

//找 第一个大于3的位置 
int find_1(int x){
    while(l < r){
        int mid = (l+r) /2;
        if(a[mid] > x) r = mid;
        else l = mid+1;
    }
    return l;
} 

int main()  
{  
    //这里是假设区间内有值。 
    //找到返回地址 找不到返回区间端点的值，比如找6返回右端点的值 
    //找4返回 0左端点的值
    //如果是端点的值，最后还有判断是否是真的值。 

    cout << find(-1);

    return 0;  
}
/*
程序运行结果： 
no
1 3
1 2
2 2
1 1
2 4
2 3
3 2

1 1
1 2
1 3
2 2
2 3
2 4
3 2
*/ 

浮点数二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

还有一种偷懒的写法 ：直接写一个for循环100次，这样相当于将区间N的除以2的100次方

int main(){
    double x; cin >> x;
    double l = 0, r = x;
    for(int i=0; i<100; i++) //
    {
        double mid = (l+r)/2;
        if(mid*mid>=x) r = mid;
        else l = mid;
    }
    printf("%llf" , l);
    return 0;
}

二分答案

二分答案与二分查找类似，即对有着单调性的答案进行二分，大多数情况下用于求解满足某种条件下的最大（小）值。

库函数

1. lower_bound(begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
2. upper_bound(begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

输出相应的结果，举例：

#include<iostream>
#include <algorithm>
using namespace std;
int main(){
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    cout<<*lower_bound(a,a+10,6)<<endl;
    cout<<*upper_bound(a,a+10,6)<<endl;
    return 0;
}
/*
6
7
*/

输出所在值的下标，举例：

#include <bits/stdc++.h>  

using namespace std;  
int a[10] = {0,0,0,1,1,2,3,3,5,5};

int main()  
{  
    int pos = upper_bound(a, a+10, 3) - a;//第一个大于3的位置 
    cout << pos << endl;//返回8

    pos = lower_bound(a, a+10, 3) - a;//第一个大于3的位置 
    cout << pos << endl;//返回6 

    return 0;  

}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com