二分法查找

二分模板

void main(){
    int l=0,r,x;

    //模板一  从左向右查找
    while(l<r){
        int mid=l+r>>1;
        if(q[mid]<x) l=mid+1;
        else r=mid;

    }

    //模板二  从右向左查找
    while(l<r){
        int mid=l+r+1>>1;
        if(q[mid]>x) r=mid-1;
        else l=mid;

    }

    return 0;
}

⭐⭐
1.模板二（从右向左）要注意加1 int mid=l+r+1>>1;

C++ 代码

#include <iostream>

using namespace std;

const int N=1e5+10;
int a[N],n,q;

int rselect(int l,int r,int x){
    while(l<r){
        int mid=l+r+1>>1;
        if(a[mid]>x) r=mid-1;
        else l=mid;
    }
    if(a[l]==x) return l;
    else return -1;


}

int lselect(int l,int r,int x){
    while(l<r){
        int mid=l+r>>1;
        if(a[mid]<x) l=mid+1;
        else r=mid;
    }

    if(a[l]==x) return l;
    else return -1;



}


int main()
{
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    while(q--){
        int k;
        cin>>k;
        cout<<lselect(0,n-1,k)<<" "<<rselect(0,n-1,k)<<endl;

    }

    return 0;
}