SUMMARY | 二分查找

package Search;

public class biSearch {
    //标准的二分查找
    public static int stdBiSearch(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<array[mid]) right=mid-1;
            else if(keyValue>array[mid]) left=mid+1;
            else return mid;
        }
        return -1;
    }
    
    //（二分法）查找第一个小于keyValue的元素
    public static int BiSearchToFindFirstSmaller(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<=array[mid]) right=mid-1;
            else left=mid+1;
        }
        return right;
    }
    
    //（二分法）查找第一个大于等于keyValue的元素
    public static int BiSearchToFindFirstBiggerorEqual(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<=array[mid]) right=mid-1;
            else left=mid+1;
        }
        return left;
    }
    
    //（二分法）查找第一个最后一个小于等于keyValue的元素
    public static int BiSearchToFindLastSmallerorEqual(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<array[mid]) right=mid-1;
            else left=mid+1;
        }
        return right;
    }
    
    //（二分法）查找第一个第一个大于keyValue的元素
    public static int BiSearchToFindFirstBigger(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<array[mid]) right=mid-1;
            else left=mid+1;
        }
        return left;
    }
    
    //（二分法）查找第一个第一个等于keyValue的元素
    public static int BiSearchToFindFirst(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<=array[mid]) right=mid-1;
            else left=mid+1;
        }
        //array[right]<keyValue<=array[left]
        if(left<length&&array[left]==keyValue) return left;
        else return -1;
    }
    
    //（二分法）查找第一个最后一个等于keyValue的元素
    public static int BiSearchToFindLast(int[] array,int keyValue) {
        int length=array.length;
        int left=0,right=length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(keyValue<array[mid]) right=mid-1;
            else left=mid+1;
        }
        //array[right]<=keyValue<array[left]
        if(right>=0&&array[right]==keyValue) return right;
        else return -1;
    }
    
    //测试样例
    public static void main(String[] args) {
        int[] a=new int[]{0,1,2,2,2,5,6};
        System.out.println(BiSearchToFindLast(a, 2));
    }
}