acwing 789. 数的范围(二分+适合理解二分边界)

题目:789. 数的范围
acwing 789. 数的范围(二分+适合理解二分边界)
思路:先用二分找到最左边的k,然后再二分找到最右边的

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int n,q;
int a[100010];

void find(int k){
    int i=0,j=n-1;
    while(i<j){
        int mid=i+j>>1;
        if(a[mid]<k)i=mid+1;
        else j=mid;
    }
    if(a[i]!=k){
        puts("-1 -1");
        return ;
    }
    int ii=i;
    j=n-1;
    while(i<j){
        int mid=i+j+1>>1;
        if(a[mid]>k)j=mid-1;
        else i=mid;
    }
    printf("%d %d\n",ii,j);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    while(q--){
        int k;
        scanf("%d",&k);
        find(k);
    }
    return 0;
}

上一篇:手撕面试官系列(二):开源框架面试题Spring+SpringMVC+MyBatis


下一篇:Centos7服务器内存使用过高排查