二分

c++

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n,q;
int arr[N];

int* binary_search(int target){
    int* res=new int[2];
    //>=target的最小值位置，不存在返回n
    int left=0,right=n;
    while(left<right){
        int mid=(left+right)/2;
        if(arr[mid]>=target){
            right=mid;
        }
        else left=mid+1;
    }
    res[0]=left;
    if(arr[left]!=target) res[0]=-1;
    left=-1,right=n-1;
    //<=target的最大值位置,不存在返回-1
    while(left<right){
        int mid=(left+right+1)/2;
        if(arr[mid]<=target){
            left=mid;
        }
        else right=mid-1;
    }
    res[1]=left;
    if(arr[left]!=target) res[1]=-1;
    return res;
}
int main(){
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++) scanf("%d ",&arr[i]);
    while(q--){
        int x;
        scanf("%d",&x);
        int* res=binary_search(x);
        printf("%d %d\n",res[0],res[1]);
        delete[] res;
    }
    return 0;
}