题目描述

给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。

对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。

如果数组中不存在该元素，则返回“-1 -1”。
输入格式

第一行包含整数n和q，表示数组长度和询问个数。

第二行包含n个整数（均在1~10000范围内），表示完整数组。

接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式

共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回“-1 -1”。
数据范围

1≤n≤100000

1≤q≤10000
1≤k≤10000

样例

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1

算法1

有单调性一定可二分，可二分的题目不一定有单调性
满足两种性质
二分一定有解，一定能二分出边界，题目可能无解
步骤：
更新区间，每次答案都在区间里，区间为1时，此为答案
再去判断，mid=l+r+1>>1（l=mid）还是mid=l+r>>1（r=mid）

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N];
int bsearch_1(int l,int r,int x)//第一个小于等于x的（即升序从后往前找）
{
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(a[mid]<=x)
            l=mid;
        else
            r=mid-1;
    }
    return l;
}
int bsearch_2(int l,int r,int x)//第一个大于等于x的（即升序从前往后找）
{
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid]>=x)
            r=mid;
        else
            l=mid+1;

    }
    return r;
}
int main()
{
    int n,q,x;
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    while(q--)
    {
        cin>>x;
        int left=bsearch_2(0,n-1,x);
        if(a[left]!=x)
            cout<<"-1 -1\n";
        else
        {
            cout<<left<<" ";
            cout<<bsearch_1(0,n-1,x)<<endl;
        }


    }
     return 0;
}