二分(算法)

原题

代码

注意：如果写之前不考虑好想要查找的是什么，十有八九会是死循环或者查找错误，就算侥幸写对了也只是运气好而已！！！

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5;
int n,q,qq;
int num[N];

int main()
{
    cin >> n >> q;
    for (int i = 0; i < n; i ++)
    {
        cin >> num[i];
        //cout << num[i];
    }
    for (int i = 0; i < q; i ++ )
    {
        cin >> qq;
        int l = 0, r = n - 1; //此处定义说明将查找的空间定为左闭右闭，与下面作对比
        while (l < r) 
        {
            int mid = l + r >> 1;
            if (num [mid] < qq) l = mid + 1;
            else r = mid;
            //cout << l;
        }
        if (num[l] != qq)
        {
            printf("-1 -1\n");
            continue;
        }
        int l1 = l, r1 = n;//此处定义说明将查找的空间定为左闭右开
        while (l1 + 1 < r1)
        {
            int mid = l1 + r1 >> 1;
            if (num[mid] <= qq) l1 = mid;
            else r1 = mid;
        }
        printf("%d %d\n", l, l1);
        
        /* 暴力o(n^2)
        //cout << qq;
        int l=-1,r=-1;
        for (int j = 0; j < n; j ++ )
        {
            if (num[j] >= qq)
            {
                if (num[j] == qq) l = j;
                else l = -1;
                break;
            }
        }
         for (int j = n-1; j > -1; j -- )
        {
            if (num[j] <= qq)
            {
                if (num[j] == qq) r = j;
                else r = -1;
                break;
            }
        }
        printf("%d %d\n",l,r);
        */
    }
    return 0;
}

35行定为左闭右开 [l1,r1)，故循环判断需为 l1 + 1 < r1。为什么得这样设置？因为如果左闭右闭，判断循环会变成 l1 < r1，这种不适用，寻找答案在左端，并且左端更新不能赋值mid+1的情况(寻找最右端的正确答案)，这个时候如果右端-左端=1，即区间大小为2，即 l1+1 = r1 ，mid = l1，会陷入一直死循环(因为这个时候mid永远等于左端即 mid = l1，然后 l1有符合条件一直循环)。所以左闭右开 [l1,r1)可以解决当 l1+1 = r1，然后mid = l1，再更新只能是 l1 = mid，不能是 l1 = mid + 1的情况。

当然也可以直接修改 “l1+1 = r1，然后mid = l1，再更新只能是 l1 = mid，不能是 l1 = mid + 1”这里面的一种情况使得左闭右闭不会循环，那就是使得mid = r1就行了，并竟左闭右闭时r1更新是 r1= mid-1，只需要mid = l1 + r1 + 1 >> 1即可。如下：

while (l1 < r1)
{
    int mid = l1 + r1 + 1>> 1;
    if (num[mid] <= qq) l1 = mid;
    else r1 = mid - 1;
}

总结

此类二分保证不死循环，保证左端+1=右端时，mid所在的那一端符合更新条件时不能自我更新(mid所在的那一端 = mid)，而是mid-1或者mid+1 赋值给那一端，可以通过修改mid所在另一端或者一端由闭区间改开区间则不会出现左端+1=右端情况出现即可

参考题解

参考题解