789. 数的范围

题目

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

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

如果数组中不存在该元素，则返回 -1 -1。

输入格式

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

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

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

输出格式

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

如果数组中不存在该元素，则返回 -1 -1。

数据范围

• $1\le n\le 100000$
• $1\le q\le 10000$
• $1\le k\le 10000$

输入样例

6 3
1 2 2 3 3 4
3
4
5

输出样例

3 4
5 5
-1 -1

解答

STL 方法

C++ 代码

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

const int N = 1e6 + 10;
int arr[N];
int n, q;

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    
    cin >> n >> q;
    for (int i = 0; i < n; i ++) {
        cin >> arr[i];
    }
    
    while (q --) {
        int k;
        cin >> k;
        
        int l = lower_bound(arr, arr + n, k) - arr;
        int r = upper_bound(arr, arr + n, k) - arr;
        
        if (l < n && arr[l] == k) {
            r -= 1;
        }
        else {
            l = -1;
            r = -1;
        }
        
        cout << l << " " << r << endl;
    }
    
    return 0;
}

手写整数二分

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n, q;
int arr[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    cin >> n >> q;
    for (int i = 0; i < n; i ++) {
        cin >> arr[i];
    }

    while (q --) {
        int k;
        cin >> k;

        int l = 0;
        int r = n;

        while (l < r) {
            int mid = l + r >> 1;

            if (arr[mid] < k) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }

        if (l >= n || arr[l] != k) {
            cout << "-1 -1" << endl;
        }
        else {
            cout << l << " ";

            l = 0;
            r = n;

            while (l < r) {
                int mid = l + r >> 1;

                if (arr[mid] <= k) {
                    l = mid + 1;
                }
                else {
                    r = mid;
                }
            }

            cout << l - 1 << endl;
        }
    }

    return 0;
}

YXC 版手写二分

C++ 代码

#include <iostream>
using namespace std;

const int N = 1e6 + 10;
int n, q;
int arr[N];

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i ++) {
        scanf("%d", &arr[i]);
    }
    
    while (q --) {
        int k;
        scanf("%d", &k);

        int l = 0;
        int r = n - 1;
        
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid] < k) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        
        if (arr[l] != k) {
            cout << "-1 -1" << endl;
        }
        else {
            cout << l << " ";
            
            l = 0;
            r = n - 1;
            
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (arr[mid] <= k) {
                    l = mid;
                }
                else {
                    r = mid - 1;
                }
            }
            cout << l << endl;
        }
    }
    return 0;
}

• 第一个是左闭右开
• 第二个是左开右闭