Problem: 年龄查询

任务总览

题目描述

有 n 位同学按照年龄从小到大排好队。

王老师想要查询，年龄为 x 的同学在队伍中首次出现的位置和最后一次出现的位置；如果队伍中不存在年龄为 x 的同学，请输出 -1 -1。

由于人数太多，一个一个数太慢了，请你编程求解。

请注意：王老师将进行 q 次查询，每次查询一个年龄 x，你需要输出该年龄在队伍中首次和最后一次出现的位置（下标从 1 开始）。

输入格式

• 第一行包含两个整数 n 和 q，表示队伍中的总人数和查询次数。
• 第二行包含 n 个正整数（均在 $[1,10000]$），表示队伍中每个人的年龄（已按非递减顺序排列）。
• 接下来 q 行，每行包含一个整数 x，表示一次查询的年龄。

输出格式

• 输出 q 行，每行包含两个整数，分别表示所查询年龄在队伍中的起始位置和终止位置（1-based）。
• 若年龄在队伍中未出现，输出 -1 -1。

输入输出示例

输入示例 1

6 3
1 2 2 2 3 3
2
1
8

输出示例 1

2 4
1 1
-1 -1

题目解析

• 使用二分查找分别定位第一个出现的位置和最后一个出现的位置。
• 因为数据已排序，可以在 $O(log n)$ 时间内完成一次查询，处理所有查询总复杂度为 $O(q log n)$。
• 注意数组下标是从 1 开始返回位置。