大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》789 题——数的范围。本文详细解析了一个基于二分查找的算法题，题目要求在有序数组中查找特定元素的首次和最后一次出现的位置。通过使用两个二分查找函数，程序能够高效地处理大量查询，时间复杂度为 O(n log n)，空间复杂度为 O(n)。文章从题目描述、算法思路、具体实现步骤到Java代码实现，全面展示了如何解决这一问题。
文章目录
❓题目描述?算法思路✅Java代码?参考
❓题目描述
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤1000001≤q≤100001≤k≤10000输入样例：
6 31 2 2 3 3 4345输出样例：
3 45 5-1 -1?算法思路
使用二分查找算法findFristGreatOrEqual(int l, int r, int x)查找数组中元素 k 的开始位置如果找到了 k 的开始位置，就返回元素 k 的开始位置，并使用findFirstLessOrEqual(int l, int r, int x)查找 k 的结束位置如果没有找到 k 的开始位置，那么也不存在 k 的结束位置。直接返回-1 -1 具体实现步骤：
初始化输入流：
程序首先创建一个StreamTokenizer 对象，用于从标准输入流中读取数据。这个对象通过 BufferedReader 和 InputStreamReader 来处理输入。 读取数组大小和查询次数：
程序调用nextInt() 方法两次，分别读取数组的大小 n 和查询次数 q。 读取数组元素：
程序使用一个循环，调用nextInt() 方法 n 次，将输入的整数依次存储到数组 nums 中。 处理每个查询：
程序使用一个循环，处理q 次查询。每次查询时，程序调用 nextInt() 方法读取一个整数 k，表示要查找的值。 查找首次出现的位置：
程序调用findFristGreatOrEqual(0, n - 1, k) 方法，使用二分查找算法在数组中查找第一个大于或等于 k 的元素的位置。如果找到的位置上的元素等于 k，则说明 k 存在于数组中。 查找最后一次出现的位置：
如果k 存在于数组中，程序调用 findFirstLessOrEqual(0, n - 1, k) 方法，使用二分查找算法在数组中查找第一个小于或等于 k 的元素的位置。这个位置即为 k 在数组中最后一次出现的位置。 输出结果：
如果k 存在于数组中，程序输出 k 的首次和最后一次出现的位置。如果 k 不存在于数组中，程序输出 -1 -1。 二分查找函数的实现：
findFristGreatOrEqual(int l, int r, int x)[l, r] 范围内查找第一个大于或等于 x 的元素的位置。通过不断缩小查找范围，最终找到目标位置。 findFirstLessOrEqual(int l, int r, int x)[l, r] 范围内查找第一个小于或等于 x 的元素的位置。通过不断缩小查找范围，最终找到目标位置。 时间复杂度：O(n log n)
空间复杂度：O(n)
✅Java代码
import java.*;public class Aw789 {// 创建一个StreamTokenizer对象，用于读取输入流static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));// 读取下一个整数static int nextInt() throws IOException {in.nextToken();return (int) in.nval;}static int n, q, k;// 定义一个数组来存储输入的数字，数组大小为100010static int[] nums = new int[100000 + 10];public static void main(String[] args) throws IOException {// 读取数组的大小n和查询次数qn = nextInt();q = nextInt();// 读取n个整数并存储到数组nums中for (int i = 0; i < n; i++) {nums[i] = nextInt();}// 处理q次查询while (q-- > 0) {// 读取查询的数字kk = nextInt();// 查找第一个大于或等于k的元素的位置int left = findFristGreatOrEqual(0, n - 1, k);// 如果找到的元素等于kif (nums[left] == k) {// 输出第一个等于k的元素的位置和最后一个等于k的元素的位置System.out.println(left + " " + findFirstLessOrEqual(0, n - 1, k));} else {// 如果没有找到等于k的元素，输出-1 -1System.out.println("-1 -1");}}}// 二分查找第一个大于或等于x的元素的位置static int findFristGreatOrEqual(int l, int r, int x) {while (l < r) {int mid = l + r >> 1; // 计算中间位置if (nums[mid] >= x) {r = mid; // 如果中间元素大于或等于x，缩小右边界} else {l = mid + 1; // 否则，缩小左边界}}return l; // 返回找到的位置}// 二分查找第一个小于或等于x的元素的位置static int findFirstLessOrEqual(int l, int r, int x) {while (l < r) {int mid = (l + r + 1) >> 1; // 计算中间位置if (nums[mid] <= x) {l = mid; // 如果中间元素小于或等于x，缩小左边界} else {r = mid - 1; // 否则，缩小右边界}}return l; // 返回找到的位置}}?参考
https://www.acwing.com/problem/content/791/作者：程序员何未来-heweilai.com
?推荐阅读
AcWing算法基础课-788逆序对的数量-Java题解AcWing算法基础课-787归并排序-Java题解博客赚钱全攻略：从新手到专家的变现之路欢迎关注我的博客：@程序员何未来，持续为你输出有价值的技术文章~
你们的点赞? 收藏⭐ 留言?️ 关注✅
是我持续创作，输出优质内容的最大动力！谢谢！
文章关键词：算法，计算机算法，算法题解，算法竞赛，Java，数据结构，AcWing算法基础课