大家好，我是何未来，本篇文章给大家讲解《AcWing算法基础课》789 题——数的范围。本文详细解析了一个基于二分查找的算法题，题目要求在有序数组中查找特定元素的首次和最后一次出现的位置。通过使用两个二分查找函数，程序能够高效地处理大量查询，时间复杂度为 <code>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≤100000

1≤q≤10000

1≤k≤10000

输入样例：

6 3

1 2 2 3 3 4

3

4

5

输出样例：

3 4

5 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;

// 定义一个数组来存储输入的数字，数组大小为100010

static int[] nums = new int[100000 + 10];

public static void main(String[] args) throws IOException {

// 读取数组的大小n和查询次数q

n = nextInt();

q = nextInt();

// 读取n个整数并存储到数组nums中

for (int i = 0; i < n; i++) {

nums[i] = nextInt();

}

// 处理q次查询

while (q-- > 0) {

// 读取查询的数字k

k = nextInt();

// 查找第一个大于或等于k的元素的位置

int left = findFristGreatOrEqual(0, n - 1, k);

// 如果找到的元素等于k

if (nums[left] == k) {

// 输出第一个等于k的元素的位置和最后一个等于k的元素的位置

System.out.println(left + " " + findFirstLessOrEqual(0, n - 1, k));

} else {

// 如果没有找到等于k的元素，输出-1 -1

System.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算法基础课