本文共 1418 字，大约阅读时间需要 4 分钟。

题目描述

给定一个按照升序排列的长度为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 31 2 2 3 3 4345输出样例：3 45 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

---

转载地址：http://rhxxn.baihongyu.com/