整数二分

思想

有单调性的一定可以二分
没有单调性的也不一定不可以二分
二分的本质是
可以划分左右取间：一个区间满足，一个不满足
保证缩的区间中一定有答案，当长度唯一的时候则一定为答案，二分一定有解，题目无解则判断一下。
步骤：
1.划分边界，取中点
2.逐步向中点左方或者右方缩小区间，直到查找完毕，只剩一个。

根据情况有两个模板

//注意边界的控制，第二个模板缩左边界时，防止死循环，需要将mid+1
bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;//l=r-1时，防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int q[N];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int j=0;j<n;j++)scanf("%d",&q[j]);
    while(m--){
        int x;
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(q[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(q[l]!=x){
        cout<<-1<<' '<<-1<<endl;    
        }
        else{
            cout<<l<<' ';
            l=0,r=n-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(q[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}