二分训练题

不一定是升序才能用二分，如果在一个位置的左右可以知道我的target得去左还是右找就可以。

二分容易死循环

只要列出来区间缩放的情况(注意重点关注lr相邻(l=r-1)后mid会导致区间缩放到哪里，就可以

C++ 代码

#include<iostream>
#include<string>
using namespace std;

//1 2 2 3 3 4 找3左
//target的左侧都是<target,右侧都是>=target
//如果mid<target说明mid不是target，缩放区域到mid+1到r
//如果mid>=target说明mid有可能是target
                      //也有可能是target右侧的数.区间放缩到 l到mid
int findl(int a[],int n,int k){
    int l=0, r=n-1;
    int mid = (l + r) / 2;


    while(l<r){
        mid = (l + r) / 2;
        if(a[mid]<k){
            l = mid + 1;
            //当r=l+1的时候，mid=l
            //l会变成l+1 也就是缩放为r,r
            //可以出循环没有问题
        }
        else{
            r = mid; 
            //当r=l+1的时候， mid=l 
            //r会变成l,缩放为l,l 
            //可以出循环没有问题
        }

    }
    return l;
}
//1 2 2 3 3 4 找3右
//target的左侧都是<=target,右侧都是>target
//如果mid<=target说明mid有可能是target，缩放区域到mid到r
//如果mid>target说明mid不可能是target放缩到 l到mid-1
int findr(int a[],int n,int k){
    int l=0, r=n-1;
    int mid = (l + r+1) / 2;
    while(l<r){
        mid = (l + r+1) / 2;
        if(a[mid]<=k){
            l = mid; 
            //如果mid是（l+r）/2，当l=r-1时，mid= r或者r-1 
            //缩放会变成从r-1/r~r
            //这个不ok由于r-1~r会出不了循环

            //如果mid是(l+r+1)/2 当l=r-1时, mid=r 
            //缩放为r,r可行了
        }
        else{
            r = mid - 1;
            //当l=r-1时，会缩放为 r-1~r-1/r-2 这个可以出循环ok 
            //如果mid是(l+r+1)/2 l=r-1时, mid=r
            //所以会缩放为r-1~r-1 这个可以出循环ok
        }
    }
    return r;
}


int main(void){
    int n, q, k;
    cin >> n >> q;
    int a[100002];
    for (int i = 0; i < n;i++){
        cin >> a[i];
    }
    for (int i = 0; i < q;i++){
        cin >> k;
        int l=findl(a, n, k);
        if(a[l]!=k){
            cout << "-1 -1" << endl;
            continue;
        }
        int r = findr(a, n, k);

        cout << l << " " << r << endl;

    }
}