思路来源: https://blog.csdn.net/WJPnb1/article/details/126360962?spm=1001.2014.3001.5502
可以合并两个模板,但是超出范围需要特判。
import java.util.Scanner;
public class T789 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int n = sc.nextInt();
int[] q = new int[len];
for (int i = 0; i < len; i++) {
q[i] = sc.nextInt();
}
while (n-- > 0) {
int k = sc.nextInt();
// (注意!!!!!)小于最小值或者大于最大值需要特判
if (k < q[0] || k > q[len - 1]) {
System.out.println("-1 -1");
continue;
}
// 寻找第一个等于k的坐标
// 套用模板
int l = -1, r = len;
//当l与r没有相接的时候,求边界
while (l + 1 != r) {
int mid = l + r >> 1;
/**
* 找第一个>=k的位置
* 划分:左边<k,右边>=k 则,
* l:最后一个<k的位置
* r:第一个>=k的位置 即所求
*/
if (q[mid] >= k) r = mid;
else l = mid;
// 这两行也可以这么写,只是换一下顺序,得到的r都是第一个>=k的位置
// 用左区间判断
/*
if(q[mid] < k) l = mid;
else r = mid;
*/
}
// 此时r的是第一个>=k的位置
// 如果不等于,说明k不存在 可以直接输出并结束方法
if (q[r] != k) {
System.out.println("-1 -1");
continue;
} else {
System.out.print(r + " ");
/**
* 现在找最后一个<=k的数字
* 划分:左边<=k,右边>k 则,
* ll:最后一个等于k的位置 即所求
* rr:第一个大于k的位置
*/
int ll = -1, rr = len;
while (ll + 1 != rr) {
int mid = ll + rr >> 1;
if (q[mid] <= k) ll = mid;
else rr = mid;
// 这两行也可以这么写,只是换一下顺序,得到的ll都是最后一个=k的位置
// 用右区间判断
/*
if(q[mid] > 5) rr = mid;
else ll = mid;
*/
}
// 此时ll一定存在,可以直接输出
System.out.println(ll);
}
}
}
}