二分的数学思想：

二分的数学思想其实就是极限，我们通过取中点的方式，不断地缩小答案所在的区间，让这个区间不断地逼近答案，类似于我们在高数中所学的极限：

一、整数二分

1、思路

我们假设想要寻找上述数轴中的左右边界。

左右边界的寻找：

我们先看左端点A：
当我们的中点满足x<=4的时候，我们就让左边界l=mid，这个mid有可能是答案的，因为l满足x<=4,mid也满足。
当我们的中点不满足x<=4的时候，我们就让右边界r=mid-1，为什么这里要减一呢？因为，mid此时满足x>4,但是l是<=4,因此，mid肯定不是答案，所以我们要减一。

我们再看右端点B：
当我们的中点满足x>=4的时候，我们就让右边界r=mid，这个mid有可能是答案的，因为l满足x>=4,mid也满足。
当我们的中点不满足x>=4的时候，我们就让左边界l=mid+1，为什么这里要加一呢？因为，mid此时满足x<4,但是l是>=4,因此，mid肯定不是答案，所以我们要加一。

此时我们看一下最关键的一点，为什么寻找左端点的时候，mid的分子上要加一，而寻找右端点的时候不需要加一？

2、模板

我们以下面的题目为例：

上述题目来自acwing网站

C++版

#include<iostream>
using namespace std;
const int N=1e6+10;
int arr[N];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&arr[i]);
    while(m--)
    {
        //输入要查找的数字
        int f=0;
        cin>>f;
        //开始二分：
        //寻找左边界
        int l=0,r=n-1;
        int mid;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(arr[mid]>=f)r=mid;
            else l=mid+1;
            
        }
        if(arr[l]!=f)cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<" ";
            //寻找右边界
            l=0,r=n-1;
           
            while(l<r)
            {

                mid=(l+r+1)>>1;
                if(arr[mid]<=f)l=mid;
                else r=mid-1;
            }
            cout<<r<<endl;
        }
    }
    
    return 0;
}

C版

#include<stdio.h>
const int N=1e6+10;

int main()
{
    int arr[N];
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&arr[i]);
    while(m--)
    {
        //输入要查找的数字
        int f=0;
        scanf("%d",&f);
        //开始二分：
        //寻找左边界
        int l=0,r=n-1;
        int mid;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(arr[mid]>=f)r=mid;
            else l=mid+1;
            
        }
        if(arr[l]!=f)printf("-1 -1\n");
        else
        {
            printf("%d ",l);
            //寻找右边界
            l=0,r=n-1;
           
            while(l<r)
            {

                mid=(l+r+1)>>1;
                if(arr[mid]<=f)l=mid;
                else r=mid-1;
            }
            printf("%d\n",r);
        }
    }
    
    return 0;
}

二、浮点数二分

1、思路：

假设我们想求一个数字的立方根，并且要保留6位小数，那么必定存在一个范围都是满足这个答案的，因为通过四舍五入后，这个范围的答案都是正确的。此时我们就可以利用浮点数二分。

所以浮点数二分的思想就是，我们让l到r所组成的区间全部落在答案所在的范围内。此时我们在输出答案即可。

来自acwing。

2、代码：

C++版

#include<iostream>
using namespace std;

double x;
double l=-10000.00;
double r=10000.00;
int main()
{
    cin>>x;
    while(r-l>1e-10)
    {
        double mid=(r+l)/2;
        if(mid*mid*mid>=x)r=mid;
        else l=mid;
    }
    printf("%.6lf",l);;
    return 0;
}

C

#include<stdio.h>

double x;
double l=-10000.00;
double r=10000.00;
int main()
{
    scanf("%lf",&x);
    while(r-l>1e-10)
    {
        double mid=(r+l)/2;
        if(mid*mid*mid>=x)r=mid;
        else l=mid;
    }
    printf("%.6lf",l);;
    return 0;
}