算法1

利用C++STL中的lower_bound(),upper_bound(),binary_search()函数对题目进行求解

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

int nums[1000050];

int main(){
    int n, q;
    cin >> n >> q;
    for(int i = 0 ; i < n; i++){
        cin >> nums[i];
    }
    while(q--){
        int k;
        cin >> k;
        if(!binary_search(nums, nums+n, k)){
            cout << "-1 -1" << endl;
            continue;
        }
        int begin = lower_bound(nums, nums+n, k) - nums;
        int e = upper_bound(nums, nums+n, k) - nums;
        cout << begin << " " << e-1 << endl;
    }
    return 0;
}

算法2

手写二分进行解题

C++ 代码

#include<iostream>
using namespace std;

int nums[100050];
int n,q;
int main(){
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    while(q--){
        int k;
        cin >> k;
        int l = 0, r = n-1;
        while(l < r){
            int mid = (l+r)/2;
            if(nums[mid] >= k) r = mid;
            else l = mid+1;
        }
        if(nums[l] != k){
            cout << "-1 -1" <<endl;
            continue;
        }else{
            cout << r << " ";
            l = r; r = n-1;
            while(l < r){
                int mid = (l+r+1)/2;
                if(nums[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }

    }
    return 0;
}