【二分2】二分找下标问题

前言

• 找到目标值第一次出现的位置
• 找到目标值最后一次出现的位置

找到目标值第一次出现的位置

题目描述：

给定一个升序排列的数组 $A$ 和 $Q$ 次询问。对于每次询问，您需要找到指定元素 $x$ 在数组中第一次和最后一次出现的位置。如果该元素不存在于数组中，则返回 $(-1, -1)$。

输入格式：

• 第一行包含两个整数 $n$ 和 $Q$，分别表示数组的长度和询问的次数。

• 第二行包含 $n$ 个整数，表示数组 $A$ 的元素，$A[i]$ ($1 \leq i \leq n$) 保证为升序排列。

• 接下来的 $Q$ 行，每行包含一个整数 $x$，表示您要查询的元素。

  $1 \leq n \leq 100000$

  $1 \leq Q \leq 10000$

输出格式：

对于每次询问，输出一行，包含两个整数，分别表示元素 $x$ 在数组中的第一次和最后一次出现的位置。如果该元素不存在，输出 $-1 -1$。

示例：

输入：

7 3
1 2 2 3 4 4 5
2
4
6

输出：

2 3
5 6
-1 -1

说明：

• 对于询问 $2$，元素 $2$ 在数组中第一次出现的位置是 $2$，最后一次出现的位置是 $3$。
• 对于询问 $4$，元素 $4$ 在数组中第一次出现的位置是 $5$，最后一次出现的位置是 $6$。
• 对于询问 $6$，元素 $6$ 不存在于数组中，因此输出 $-1 -1$。