【二分】BISHI85 【模板】整数域二分

思路求解代码publicstaticvoidmain(String[]args)throwsIOException{// 使用BufferedReader读取输入PrintWriter输出结果BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));PrintWriteroutnewPrintWriter(newOutputStreamWriter(System.out));// 读取第一行输入分割成字符串数组String[]strAbr.readLine().trim().split(\\s);// 解析数组长度n和查询次数qintnInteger.parseInt(strA[0]);intqInteger.parseInt(strA[1]);// 创建数组a并读取输入数据int[]anewint[n];String[]strBbr.readLine().trim().split(\\s);for(inti0;in;i){a[i]Integer.parseInt(strB[i]);}// 对数组进行排序为后续查询做准备Arrays.sort(a);// 处理q次查询while(q--0){// 读取每次查询的左右边界String[]strCbr.readLine().trim().split(\\s);intlInteger.parseInt(strC[0]);intrInteger.parseInt(strC[1]);// 使用二分查找计算下界和上界intleftlowerBound(a,l);intrightupperBound(a,r);// 输出结果范围内的元素个数out.println(right-left);}// 关闭IO资源out.flush();out.close();br.close();}/** * 二分查找下界函数 * * param a 已排序的数组 * param target 目标值 * return 第一个大于等于target的元素的索引 */privatestaticintlowerBound(int[]a,inttarget){// 初始化查找范围的 low 和 high 指针// low 从数组的起始位置 0 开始// high 从数组长度开始不包括该位置intlow0,higha.length;// 当 low 小于 high 时继续查找// 这是循环查找的条件确保查找范围有效while(lowhigh){// 计算中间位置 mid// 使用位运算 (high-low)1 代替除法 2提高效率// 防止整数溢出同时确保 mid 总是在 low 和 high 之间intmidlow((high-low)1);// 如果中间位置的元素大于等于目标值// 说明目标值可能在左半部分或者 mid 就是我们要找的位置// 因此将 high 设置为 mid继续在左半部分查找if(a[mid]target){highmid;}else{// 如果中间位置的元素小于目标值// 说明目标值一定在右半部分// 因此将 low 设置为 mid1继续在右半部分查找lowmid1;}}// 当循环结束时low 指向第一个大于等于 target 的元素的位置// 如果所有元素都小于 target则返回数组长度returnlow;}/** * 二分查找上界函数 * * param a 已排序的数组 * param target 目标值 * return 第一个大于target的元素的索引 */privatestaticintupperBound(int[]a,inttarget){// 初始化查找范围的左右边界左边界为0右边界为数组长度intlow0,higha.length;// 当左边界小于右边界时继续查找while(lowhigh){// 计算中间位置使用位运算防止溢出intmidlow((high-low)1);// 如果中间位置的值大于目标值则上界在左半部分if(a[mid]target){highmid;}else{// 否则上界在右半部分且不包括中间位置lowmid1;}}// 返回第一个大于target的元素的索引returnlow;}