c++整数二分代码实现

整数二分的本质：

如果有单调性，一定可以二分，但是可以二分的题目不一定有单调性，本质并不是单调性

本质是就是有一个区间，然后有一个性质，左半边区间不满足，右半边区间满足，

如果找到这个可以把整个区间一分为二的性质，我们就可以用二分寻找这两个区间的边界

把这两个性质的区间分离出来

一，如何二分出来左边区间的边界点

步骤一：找一个中间值mid=（l+r+1）/2；

步骤二：检查这个mid是不是满足左边区间的性质，如果满足，那么它的边界点一定是在mid和r之间，然后更新l=mid，再取中间值，

如果不满足，那么它的边界点一定是在l和mid-1之间，然后更新r=mid-1，再取中间值。

二，如何二分出来右边区间的边界点

步骤一：找一个中间值mid= (l+r)/2；

步骤二：检查这个mid是不是满足右边区间的性质，如果满足，那么他的边界点一定是在l和mid之间，然后更新l=mid，再取中间值

如果不满足，那么他的边界点一定是在mid+1和r之间，然后更新r=mid+1，再取中间值

为什么要加一，防止死循环，具体举例吧

每次先写一个mid，然后写一个check函数，根据check函数的结果具体划分

如果else后面跟的是mid-1，那么就需要在中间值内里改成mid=（l+r+1）/2；

做题技巧：可以画图方便理解

标好点。

对于我自己的理解就是不断卡区间，来确定答案的最终坐标

代码实现

 #include<iostream>
 using namespace std;
 const int N=1e6+10;
 int p[N];
 int n,m;
 int main (void)
 {
     scanf("%d%d",&n,&m);
     int i;
     for(i=0;i<n;i++)
     {
         scanf("%d",&p[i]);    
    }
    while(m--)
    {
        int x;
        scanf("%d",&x);
        
        int l=0;
        int r=n-1;
        //左边界 
        while(l<r)
        {
            int mid =(l+r)/2;//到底需不需要加一，我们后面再想
            if(p[mid]>=x)
            {
                r=mid;
            } 
            else
            {
                l=mid+1;//mid已经不可能了，所以mid+1 
            }
        }
        if(p[l]!=x)
            {
                printf("-1 -1\n");
            }
            else
            {
                printf("%d ",l);
                //直接在这里继续写另一个值
                int l=0;int r=n-1;
                while(l<r)
                {
                    int mid = (l+r+1)/2;
                    if(p[mid]<=x)
                    {
                        l=mid;    
                    }
                    else
                    {
                        r=mid-1;
                    }
                }
                printf("%d\n",l); 
            }
    }
     return 0;
 }