题目描述

给定一个按照升序排列的长度为 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

整数二分

时间复杂度

$O(1)$

参考文献

C++ 代码

#include<iostream>
using namespace std;

const int N = 100010;
int n, k;
int q[N];

int main(){

    scanf("%d%d", &n,&k);
    for(int i=0;i<n;i++) scanf("%d", &q[i]);

    // 判断一个元素的起始位置和终止位置，可以以此作为两个边界点用两个性质将数列分成两个部分
    // 起始位置作为边界：则右边的数都大于等于该数，相当于找大于等于该数的边界点   模板二
    // 终止位置作为边界点：则左边的数都小于等于该数，相当于找小于等于该数的边界点 模板一
    int l,r;
    while(k--){
        int x;
        scanf("%d", &x);
        // 起始点
        l=0, r=n-1;     // 此处必须重新定义l,r的值
        while(l<r){
            int mid= (l + r) / 2;
            if(q[mid]>=x) r=mid;
            else l=mid+1;
        }
         if(q[l]!=x) cout<<"-1 -1"<<endl;
         else {
             cout<<l<<" ";
             // 终止点
             l=0,r=n-1;
             while(l<r){
                 int mid=(l+r+1)/2;
                 if(q[mid]<=x) l=mid;
                 else r=mid-1;
             }
             cout<<l<<endl;
         }
    }
}

算法2

暴力枚举

时间复杂度

此时会超时
$$O(n)$$

C++ 代码

#include<iostream>
using namespace std;

const int N = 100010;
int n, k;
int q[N];

int main(){

    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++)scanf("%d", &q[i]);

    while(k--){
        int x;
        scanf("%d", &x);
        int min=-1,max=-1;
        for(int i=0;i<n;i++){
            if(i==0 && q[i]==x) min=0;
            else if(i==n-1 && q[i]==x) max=n-1;
            else
            {
                if(i!=0 && i!=n-1){
                    if(q[i]==x && q[i-1]<x) min=i;
                    if(q[i]==x && q[i+1]>x) max=i;

                }

            }
        }
        if(min==-1 && max==-1)cout<<"-1 -1"<<endl;
        else{
            if(min==-1) min=max;
            else if(max==-1) max=min;
            cout<<min<<" "<<max<<endl;
        }
    }
}