题目描述

在一个含有重复有序数列里，查找目标值的区间下标，没有返回负一

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

正解 二分查找 O(klogn)

y总的算法基础课:

check函数关注的性质使得a[mid]落在左边那么`l=mid,r=mid-1`,且`mid=l+r+1>>1`;
check函数关注的性质使得a[mid]落在右边那么`r=mid,l=mid+1`,且`mid=l+r>>1`;

细节：

为了使得查找简单，这里全部使用严格的大于和小于。即所得结果是目标下标的左一个和右一个。
故初始化要从极端情况，从取不到的-1，N开始。

C++ 代码

#include<iostream>
using namespace std;

#define loop(x) for(int i=0;i<x;++i)
#define read(x) scanf("%d",&x)

int n,k;
int a[100003];

int bs(int goal,int type){
    //可能序列是N个相同的数，从极端两侧出发
    int l=-1;
    int r=n;

    if(type==1){
        while(l<r){
            int mid=l+r+1>>1;
            if(a[mid]<goal) l=mid;//比目标值小
            else r=mid-1;
        }
        l++;
    }else{
        while(l<r){
            int mid=l+r>>1;
            if(a[mid]>goal) r=mid;//比目标值大
            else l=mid+1;
        }
        --l;
    }

    if(a[l]!=goal) return -1;//不含这个值
    return l;
}



int main(){

    read(n);read(k);
    loop(n) read(a[i]);

    loop(k){
        int x;read(x);
        cout<<bs(x,1)<<" "<<bs(x,2)<<endl;
    }


    return 0;
}