题目描述
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
数据范围
1≤n≤100000
1≤n≤100000
1≤q≤10000
1≤q≤10000
1≤k≤10000
1≤k≤10000
样例
输入样例： 6 3 1 2 2 3 3 4 3 4 5 输出样例： 3 4 5 5 -1 -1
优化二分查找跳过重复元素
此题采用正常的二分查找会超时，但我们可以注意到，此题有很多重复的数字例如（111223333）
我们二分查找时左边查找到第一个1的时候就可以跳过其余的1
可以通过一个数组来实现记录重复数字的个数，在二分查找时可以直接跳过
java代码
package 蓝桥; import java.util.Scanner; /****** * * @author genji * 此题采用正常的二分查找会超时，但我们可以注意到，此题有很多重复的数字例如（111223333） * 我们二分查找时左边查找到第一个1的时候就可以跳过其余的1 * 可以通过一个数组来实现记录重复数字的个数，在二分查找时可以直接跳过 */ public class 数的范围_789 { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(),m=scanner.nextInt(); int[] a=new int[n]; int[] b=new int[n];//b中存放重复数字的数量，因为下面采用二分查找所以有前后两个标志 //例如a 中的数为1,1,1,1,1,2,2,2,2,3,3,4,4,4,4,5 //则b中的数为 5,0,0,0,5,4,0,0,4,2,2,4,0,0,4,1 //使其在查找时跳过重复的数字 int c=0,i; for (i = 0; i < n; i++) { a[i]=scanner.nextInt(); if (i==0||a[i]==a[i-1]) { c++; //如果是第一个数或者和前面数字相同的数则记录相同数字的个数 } else if (a[i]!=a[i-1]) { b[i-1]=c; b[i-c]=c; //将相同数字个数赋到b数组相同下标的头和尾 c=1; } } b[i-1]=c; b[i-c]=c; for (i = 0; i < b.length; i++) { System.out.println(b[i]); } while (m-->0) { int l=0,r=n-1; int q=scanner.nextInt(); while (l<r) { if (a[l]!=q) { l+=b[l];// 跳过重复的数字 } if (a[r]!=q) { r-=b[r];// 跳过重复的数字 } if (a[r]==q&&a[l]==q) { System.out.println(l+" "+r); break; } } if(a[l]!=q&&a[r]!=q) { System.out.println(-1+" "+-1); } } } }
