整数二分——比想象中的难

（y总太强力orz） 来看一道这样的题： 给出一个单调不减数列，对这个数列提出q次问询，每一次问询给出一个数列中的元素x，求：

1. 第一个大于x的元素
2. 第一个大于等于x的元素
3. 最后一个小于x的元素
4. 最后一个小于等于x的元素

整数二分往往面临着非常复杂的临界情况和边界判断问题，这便是其蛋疼的情况，网上对于这一类问题有多种写法，我介绍两种较为好理解的，这篇是其中之一，即yxc大神的二分模板

//1
while(L<R){
    mid=L+R>>1;
    if(check(mid))
        L=mid+1;
    else    R=mid;
}
//2
while(L<R){
    mid=L+R+1>>1;
    if(check(mid))
        R=mid-1;
    else    L=mid;
}

这两种模板的区别主要在于取mid时向上还是向下，和在二分时缩小R边界还是缩小L边界 先说结论：缩小L边界时，mid向下取整，缩小R边界时，mid向上取整这主要是避免一类问题，请看//2的代码：当L=R-1时，mid本应向上取整到R，但是如果漏加了1，则会变成向下取整的L，此时如果check为false，执行L=mid，区间没有变，就会陷入死循环

我们将二分可以理解为一个区间的染色问题，对于一个红蓝两色的区间，我们希望找出红蓝分界点——注意，整数二分中，红蓝分界点是不同的，即红色末尾和蓝色开头不是一个位置 在开始操作前，我们认为整个线段都是灰色的 每次取得一点mid时，如果mid是红色，则可以得出mid又侧全部是红色，而如果是蓝色，则可以得出mid以左全是蓝色，这样我们就可以以logN的效率快速染色

而L，R的调整取决于我们要求的问题——是蓝色末尾？红色开头？ 我们以查询红色开头为例： 在每一次取得mid时，都应查询a[mid]的颜色 如果为蓝色，则L=mid+1，为什么加1？mid不可能是答案，我们要缩小所查询的范围 如果为红色，此时应该R=mid,此时不减1的理由是，因为我们想查询红色开头，此时的mid可能是答案，不能漏掉了 而在我们根据问题确定好区间变化时，mid的取整规则也随之确定了，此时问题得到解决

简而言之：

1. 确定问题
2. 写出L，R变化规则
3. 根据L，R的变化确定mid取整规则

以上三步大概可以解决大部分二分问题了吧 贴上原问题的代码:

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

const int N=2e5+10;
int a[N];

int main(){
    //找到第一个大于x的元素，第一个大于等于x的元素
    //最后一个小于x的元素，最后一个小于等于x的元素
    //1 2 2 3 3 3 4 5 5 6 6 6 6 6 7
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while(q--){
        int x;
        scanf("%d",&x);
        int L=1,R=n,mid;
        //第一个大于x的元素
        while(L<R){
            int mid=L+R>>1;
            if(a[mid]<=x)
                L=mid+1;
            else
                R=mid;
        }
        printf("第一个大于%d的元素是a[%d]=%d\n",x,L,a[L]);
        //第一个大于等于x的元素
        L=1,R=n;
        while(L<R){
            int mid=L+R>>1;
            if(a[mid]<x)
                L=mid+1;
            else
                R=mid;
        }
        printf("第一个大于等于%d的元素是a[%d]=%d\n",x,L,a[L]);
        //最后一个小于x的元素
        L=1,R=n;
        while(L<R){
            int mid=L+R+1>>1;
            if(a[mid]>=x)
                R=mid-1;
            else
                L=mid;
        }
        printf("最后一个小于%d的元素是a[%d]=%d\n",x,L,a[L]);
        //最后一个小于等于x的元素
        L=1,R=n;
        while(L<R){
            int mid=L+R+1>>1;
            if(a[mid]>x)
                R=mid-1;
            else
                L=mid;
        }
        printf("第一个小于等于%d的元素是a[%d]=%d\n",x,L,a[L]);
    }
    return 0;
}

另外，BV1d54y1q7k7介绍的另一种写法也相当有意思，过几天有时间了我会照着模拟几遍然后写出来