package Week4; public class BinarySearch { //有重复值时二分查找的API返回的是第一个数的下标 public static void main(String[] args) { //0,1,2,3,4,5,6,7,8,9,10,11,12 int arr[] = new int[]{1,1,2,3,4,4,4,5,6,7,8, 8,9};//12 int start = downBinarySearch(arr,0,12,8);//找第一个4的位置 System.out.println(start); int end = upBinarySearch(arr,0,12,8);//找第二个8的位置 System.out.println(end); } //找下限,找有重复值的第一个数的下标,即找第一个4的下标 private static int downBinarySearch(int[] arr, int l, int r,int target) { while(l<r) { int m = (l+r)/2; if(arr[m]>=target) { r=m; }else { l=m+1; } } return l; } //1.找下限,找有重复值的最后一个数的下一个数的下标比如1,1,2,3,4,4,4,5,6,7,8, 8,9找第二个8返回12 //如果最后重复数字的下一位没有数字,比如8就是最后一位,返回的就是当前8的下标 //2.找下限,找有重复值的最后一个数的下一个数的下标比如1,1,2,3,4,4,4,5,6,7,8, 8找第二个8返回当前8的下标11=======需要特殊处理一下 //如果最后重复数字的下一位有数,比如8的下一位有数返回的就是8的下一位数的下标 private static int upBinarySearch(int[] arr, int l, int r,int target) { while(l<r) { int m = (l+r)/2; if(arr[m]<=target) { l = m+1; }else { r = m; } } return l; } }View Code