利用二分
难点是要理解二分最后退出的时候,l与r是相等的。
左右两边查找,查找左边的时候,看似是找的左边,实则首先找的是整个数据。如果左边都没找到,那么最后data[r]==x也是肯定不成立的。
左边找完了,l
与r
相等的。此时l
不变,将r
放到数据的末尾。即可开始查找右边第一次出现的位置。由于数据是递增的,末尾开始一直到需要找的x,都比x大,只需要找到右边的肯定要找第一个 比x小的数。
import java.io.*;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static int n,q;
static int[] data = null;
public static void main(String[] args) throws IOException{
in.nextToken();
n = (int)in.nval;
in.nextToken();
q = (int)in.nval;
data = new int[n];
for(int i=0;i<n;i++){
in.nextToken();
data[i] = (int)in.nval;
}
while(q>0){
in.nextToken();
int x = (int)in.nval;
int l=0,r=n-1;
// 左边找最大的
while(l<r){
int mid = l+r >>1;
if(data[mid]>=x) r=mid;
else l = mid + 1;
}
if(data[r]==x){
out.write(r+" "); // 输出左边
r = n-1;
while(l<r){
int mid = l+r+1 >>1;
if(data[mid]<=x) l=mid;
else r = mid-1;
}
out.write(l+"\n");
}
// 如果没找到,说明整个数组中都没有该数
else out.write("-1 -1\n");
q--;
}
out.flush();
}
}