AcWing 789. 数的范围 Java 整数二分
原题链接
简单
作者:
天乔巴夏丶
,
2021-01-18 17:04:00
,
所有人可见
,
阅读 284
import java.util.Scanner;
class Main {
static int n, q;
static int[] nums;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
q = sc.nextInt();
nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
while (q -- > 0) {
int k = sc.nextInt();
int[] arr = solve(nums, k);
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
private static int[] solve(int[] nums, int k) {
// 找到第一个大于等于k的
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = l + r >>> 1;
if(nums[mid] >= k){
r = mid;
}else {
l = mid + 1;
}
}
if(nums[r] != k) return new int[]{- 1, - 1};
int begin = l;
l = 0;
r = nums.length - 1;
while(l < r){
int mid = l + r + 1 >>> 1;
if(nums[mid] <= k){
l = mid;
}else{
r = mid - 1;
}
}
int end = l;
return new int[]{begin, end};
}
}