题目描述
给定一个按照升序排列的长度为 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
java 代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
final int N = 100010; // 定义一个常量N
int n = scanner.nextInt(); // 读取数组长度
int m = scanner.nextInt(); // 读取查询次数
int[] arr = new int[N]; // 创建一个大小为N的数组
for (int i = 0; i < n; i++) { // 读取输入的数组元素
arr[i] = scanner.nextInt();
}
while (m-- > 0) { // 对每一个查询进行处理
int x = scanner.nextInt(); // 读取要查询的值
int l = 0, r = n - 1; // 初始化左右边界
while (l < r) { // 二分查找左边界
int mid = l + (r - l) >> 1; // 计算中间位置
if (arr[mid] >= x) { // 若中间值大于等于要查找的值
r = mid; // 缩小右边界
} else {
l = mid + 1; // 缩小左边界
}
}
if (arr[l] != x) { // 如果找到的左边界的值不等于x
System.out.println("-1 -1"); // 输出"-1 -1"表示未找到
} else {
int start = l, end = 0, r = n - 1; // 初始化查找右边界的变量
while (l < r) { // 二分查找右边界
int mid = l + (r - l + 1) >> 1; // 计算中间位置
if (arr[mid] <= x) {
l = mid; // 缩小左边界
} else {
r = mid - 1; // 缩小右边界
}
}
int end = l; // 找到右边界
System.out.println(start + " " + end); // 输出左右边界
}
}
scanner.close(); // 关闭Scanner
}
}
过程模拟
数组:[1, 2, 2, 3, 3, 4]
1. 查询值为 3
二分查找左边界:
数组 [1, 2, 2, 3, 3, 4]
初始化左右边界 l = 0, r = 5
中间索引 mid = 0 + (5 - 0) >> 1 = 2
中间值 arr[mid] = 2
因为 arr[mid] < x (3), 更新左边界 l = mid + 1 = 3
二分查找右边界:
数组 [1, 2, 2, 3, 3, 4]
初始化左右边界 l = 3, r = 5
中间索引 mid = 3 + (5 - 3) >> 1 = 4
中间值 arr[mid] = 3
因为 arr[mid] >= x (3), 更新右边界 r = mid = 4
此时,左边界为索引 3,右边界为索引 4。输出范围为 3 到 4。
查询值为 4
二分查找左边界:
数组 [1, 2, 2, 3, 3, 4]
初始化左右边界 l = 0, r = 5
中间索引 mid = 0 + (5 - 0) >> 1 = 2
中间值 arr[mid] = 2
因为 arr[mid] < x (4), 更新左边界 l = mid + 1 = 3
二分查找右边界:
数组 [1, 2, 2, 3, 3, 4]
初始化左右边界 l = 3, r = 5
中间索引 mid = 3 + (5 - 3) >> 1 = 4
中间值 arr[mid] = 3
因为 arr[mid] < x (4), 更新左边界 l = mid + 1 = 5
此时,左边界为索引 5,右边界为索引 5。输出范围为 5 到 5。
查询值为 5
二分查找左边界:
数组 [1, 2, 2, 3, 3, 4]
初始化左右边界 l = 0, r = 5
中间索引 mid = 0 + (5 - 0) >> 1 = 2
中间值 arr[mid] = 2
因为 arr[mid] < x (5), 更新左边界 l = mid + 1 = 3
二分查找右边界:
数组 [1, 2, 2, 3, 3, 4]
初始化左右边界 l = 3, r = 5
中间索引 mid = 3 + (5 - 3) >> 1 = 4
中间值 arr[mid] = 3
因为 arr[mid] < x (5), 更新左边界 l = mid + 1 = 5
此时,无法找到查询值 5 在数组中的范围。输出 "-1 -1" 表示未找到。