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

https://www.acwing.com/problem/content/791/

#include<bits/stdc++.h>
using namespace std;

int main() {

    int n;
    int k;
    int t;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<k;i++) {
        cin>>t;

        int mid;

        int l=0,r=n-1;
        while(l<r) {
            mid=l+r>>1;
            if(t>a[mid]) l=mid+1;
            else r=mid;
        }
        if(a[l]!=t) {
            printf("-1 -1\n");
            continue;
        }
        printf("%d ",l);
        l=0, r=n-1;
        while(l<r) {
            mid=l+r+1>>1;
            if(t<a[mid]) r=mid-1;
            else l=mid;
        }
        printf("%d\n",r);
    }
    return 0;
}