AcWing 789. 数的范围

题目描述
给定一个按照升序排列的长度为 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
分析：
题面很好懂
查询q次连续元素的开始和结束位置（因为是单调升序）。
现在就讨论对于一次查询来说，
如何在最短的时间内实现查询。
因为元素k的开始和结束位置就是在数组中从左往右第一个k的下标和最后一个k的下标；
起止位置和终止位置这两个东西，可以当作是对于一个元素k的两次查找：

1一次查找大于等于k的数中下标最小的数并记录其下标（也就是第一个k的下标）；
2一次查询小于等于k的数中下标最大的数并记录其下标（也就是最后一个k的下标）
所以判断mid是否符合的判断条件不就有了吗；
对于第一个元素k的开始位置：

    mid=l+r>>1;
    if(num[mid]<a) l=mid+1;
    else r=mid;

对于最后一个：

    mid=l+r+1>>1;
    if(num[mid]>a) r=mid-1;
    else l=mid;

对于每一次对于元素k的查询就是

int yef(int a)//查询结束位置
{
    int l=0,r=n-1;
    int mid;
    while(r>l)
    {
        mid=l+r+1>>1;
        if(num[mid]>a) r=mid-1;
        else l=mid;
    }
    if(num[l]==a) return l;//因为最后找完后l的位置上就是元素结束的位置，所以若存在这个元素，这一位上必定也是这个元素；
    else return -1;//若这一位上不是 返回-1；
}
int zef(int a)//查询开始位置
{
    int l=0,r=n-1;
    int mid;
    while(r>l)
    {
        mid=l+r>>1;
        if(num[mid]<a) l=mid+1;
        else r=mid;
    }
    if(num[l]==a) return l;
    else return -1;
}

java代码

import java.io.*;
public class Main {
    static int n;
    static int q;
    public static void main(String[] args) throws IOException{
        StreamTokenizer re=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        re.nextToken();n=(int)re.nval;
        re.nextToken();q=(int)re.nval;
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            re.nextToken();a[i]=(int)re.nval;
        }
        while(q--!=0){
            re.nextToken();int target=(int)re.nval;
            int l=0,r=n-1;//一开始把下标两个写反了，在idea调试的时候才发现
            while(l<r){
                int mid=l+r >> 1;
                if(a[mid]>=target){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
            if(a[l]!=target){
                System.out.println("-1 -1");
            }else{//第一个下标都找不到就要直接退出了
             System.out.print(l+" ");
             l=0;
             r=n-1;
             while(l<r){
                int mid=l+r+1 >> 1;
                if(a[mid]<=target){
                    l=mid;
                }else{
                    r=mid-1;
                }
            }
            System.out.println(l);

            }
        }
    }
}

完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int num[100001];
int yef(int a)
{
    int l=0,r=n-1;
    int mid;
    while(r>l)
    {
        mid=l+r+1>>1;
        if(num[mid]>a) r=mid-1;
        else l=mid;
    }
    if(num[l]==a) return l;
    else return -1;
}
int zef(int a)
{
    int l=0,r=n-1;
    int mid;
    while(r>l)
    {
        mid=l+r>>1;
        if(num[mid]<a) l=mid+1;
        else r=mid;
    }
    if(num[l]==a) return l;
    else return -1;
}
int main()
{
    cin>>n>>m;
    int ck;
    int id;
    for(int i=0;i<n;i++) cin>>num[i];
    for(int i=1;i<=m;i++)//对于每一个数的查找
    {
        cin>>ck;
        id=zef(ck);
        cout<<id<<' ';
        id=yef(ck);
        cout<<id<<endl;
    }
    return 0;
}