给定一个长度为 n 的升序整数数组和 q 次查询，每次查询要求输出某个值 k 在数组中第一次和最后一次出现的位置（下标从 0 开始）。若该值不存在，则返回 -1 -1。

本题的核心在于高效地定位目标值的左右边界。由于数组已排序，可以利用二分查找将每次查询的时间复杂度控制在 O(log n) 级别。

算法思路

我们需要分别实现两个独立的二分过程：

• 查找左边界：寻找第一个等于 k 的位置。在二分过程中，若中间元素 a[mid] 大于等于 k，则右边界收缩至 mid；否则左边界移动到 mid + 1。
• 查找右边界：寻找最后一个等于 k 的位置。此时若 a[mid] 小于等于 k，则左边界移动至 mid；否则右边界设为 mid - 1。注意此处 mid 需采用上取整方式计算，防止死循环。

关键细节

• 当左边界未找到目标值时，无需进行右边界搜索，直接返回 -1 -1。
• 计算中点时，l + r >> 1 用于下取整（查找左边界），而 l + r + 1 >> 1 实现上取整（查找右边界），避免在区间长度为 2 时陷入无限循环。

C++ 实现

#include <iostream>
using namespace std;

const int MAXN = 100010;
int arr[MAXN];
int length, queryCount;

int main() {
    scanf("%d%d", &length, &queryCount);
    for (int i = 0; i < length; ++i) {
        scanf("%d", &arr[i]);
    }

    while (queryCount--) {
        int target;
        scanf("%d", &target);

        // 查找最左出现位置
        int left = 0, right = length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        if (arr[left] != target) {
            printf("-1 -1\n");
        } else {
            int leftBound = left;

            // 查找最右出现位置
            left = 0, right = length - 1;
            while (left < right) {
                int mid = (left + right + 1) >> 1;
                if (arr[mid] <= target) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            printf("%d %d\n", leftBound, right);
        }
    }

    return 0;
}

输入输出示例

输入：

6 3
1 2 2 3 3 4
3
4
5

输出：

3 4
5 5
-1 -1

数据范围

• 1 ≤ n ≤ 100000
• 1 ≤ q ≤ 10000
• 1 ≤ k ≤ 10000