二分查找练习

牛可乐和魔法封印

链接：https://ac.nowcoder.com/acm/problem/235558 来源：牛客网

此题是二分查找，并且考虑到可能有相同的值，就采用了二分查找边界值

import java.util.Scanner;

//牛可乐和魔法封印
public class Main{
	public static void main(String[] args) {
		int n;
		Scanner scan = new Scanner(System.in);
		n=scan.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i]=scan.nextInt();
		}
		int q;
		q=scan.nextInt();
		while(q!=0) {
			int x,y;
			x=scan.nextInt();
			y=scan.nextInt();
			//定义最大左下标
			int leftIndex=left(a,x);
			//定义最小右下标
			int rightIndex=right(a,y);
			System.out.println(rightIndex-leftIndex+1);
			q--;
		}
		scan.close();
	}
	//左下标
	public static int left(int[] a,int target) {
		int i,j;
		i=0;
		j=a.length-1;
		while(i<=j) {
			int m=(i+j)>>>1;//右移一位，相当于/2
			if(target<=a[m]) {
				j=m-1;
			}else {
				i=m+1;
			}
		}
		return i;//返回右下标,如果有重复元素返回最小的下标
	}
	//右下标
	public static int right(int[] a,int target) {//a为所查数组，target为查询目标值
		int i,j;
		i=0;
		j=a.length-1;
		while(i<=j) {
			int m=(i+j)>>>1;//右移一位，相当于/2
			if(target<a[m]) {
				j=m-1;
			}else {
				i=m+1;
			}
		}
		return j;//返回右下标，如果有重复元素返回最大的下标
	}
}