首页 > 代码库 > 再探二分查找

再探二分查找

public class BiSearchChangeMode1{    public static void main(String args[]){        double[] a = {1,2.5,2.5,2.5,2.5,2.5,3,4,4,4,5};        int len = a.length;        double key = 25; //四组测试数据(-2,2,2.5,25)                int resIndex = getTheMinThanKey(a,len,key,0,len-1);        System.out.println("+++++++++++++++++++++++++++++++++++");        System.out.println("1.在一个有序的数组中,找到一个最小的比key大的数(即,第一个比key大的数)");        if(resIndex != -1){            System.out.println("\t数组的下标为:" + resIndex);            System.out.println("\t数组的值为:" + a[resIndex]);        }else{            System.out.println("\t数组中没有满足条件的值");        }                        System.out.println("+++++++++++++++++++++++++++++++++++");        System.out.println("2.在一个有序的数组中,找到和key相等的最小下标的数(即,第一个和key相等的数)");        resIndex = getTheFirstEqualsNum(a,len,key,0,len-1);        if(resIndex != -1){            System.out.println("\t数组的下标为:" + resIndex);            System.out.println("\t数组的值为:" + a[resIndex]);        }else{            System.out.println("\t数组中没有满足条件的值");        }                System.out.println("+++++++++++++++++++++++++++++++++++");        System.out.println("3.在一个有序的数组中,找到和key相等的最大下标的数(即,最后一个和key相等的数)");        resIndex = getTheLastEqualsNum(a,len,key,0,len-1);        if(resIndex != -1){            System.out.println("\t数组的下标为:" + resIndex);            System.out.println("\t数组的值为:" + a[resIndex]);        }else{            System.out.println("\t数组中没有满足条件的值");        }                System.out.println("+++++++++++++++++++++++++++++++++++");        System.out.println("4.在一个有序的数组中,找到和key相等的数(任意一个),不存在则返回-1");        resIndex = getAnyEqualsNum(a,key,0,len-1);        if(resIndex != -1){            System.out.println("\t数组的下标为:" + resIndex);            System.out.println("\t数组的值为:" + a[resIndex]);        }else{            System.out.println("\t数组中没有满足条件的值");        }        System.out.println("+++++++++++++++++++++++++++++++++++");        System.out.println("5.在一个有序的数组中,找到一个最大的比key小的数(即,最后一个比key小的数)");        resIndex = getTheMaxLessKey(a,len,key,0,len-1);        if(resIndex != -1){            System.out.println("\t数组的下标为:" + resIndex);            System.out.println("\t数组的值为:" + a[resIndex]);        }else{            System.out.println("\t数组中没有满足条件的值");        }    }    /**    * 1 在一个有序的数组中,找到一个最小的比key大的数(即,第一个比key大的数)    */    public static int getTheMinThanKey(double[] a,int len,double key,int low,int high){        //1:如果第一个数就比key大        if(a[0]>key){            return 0;        }        //2:如果最后一个数不大于key        if(a[len-1]<=key){            return -1;        }        //3 :其他情况        if(high>=1 && a[high]>key && a[high-1]<=key){            return high;        }        while(low < high-1){            int mid = low + (high-low)/2;            if(a[mid]>key)                high = mid;            else                 low = mid;        }        return getTheMinThanKey(a,len,key,low,high);    }    /**    * 2 在一个有序的数组中,找到和key相等的最小下标的数(即,第一个和key相等的数)    */    public static int getTheFirstEqualsNum(double[] a,int len,double key,int low,int high){        //1:没有满足条件的        if(low>high){            return -1;        }        //2:第一个数即满足条件时        if(a[0] == key){            return 0;        }        //3:其他情况        if(high>=1 && a[high]==key && a[high-1] != key){            return high;        }        while(low<=high){            int mid = low + (high-low)/2;            if(a[mid]>key)                high = mid-1;            else if(a[mid]<key)                low = mid+1;            else{                high = mid;                break;            }        }        return getTheFirstEqualsNum(a,len,key,low,high);    }    /**    * 3 在一个有序的数组中,找到和key相等的最大下标的数(即,最后一个和key相等的数)    */    public static int getTheLastEqualsNum(double[] a,int len,double key,int low,int high){        //1:没有满足条件的        if(low>high){            return -1;        }        //2:最后一个数即满足条件时        if(a[len-1] == key){            return len-1;        }        //3:其他情况        if(low<len-1 && a[low]==key && a[low+1] != key){            return low;        }        while(low<=high){            int mid = low + (high-low)/2;            if(a[mid]>key)                high = mid-1;            else if(a[mid]<key)                low = mid+1;            else{                low = mid;                break;            }        }        return getTheLastEqualsNum(a,len,key,low,high);    }    /**    * 4 在一个有序的数组中,找到和key相等的数(任意一个),不存在则返回-1    */    public static int getAnyEqualsNum(double[] a,double key,int low,int high){        while(low<=high){            int mid = low + (high-low)/2;            if(a[mid]>key){                high = mid - 1;            }else if(a[mid]<key){                low = mid + 1;            }else{                return mid;            }        }        return -1;    }    /**    * 5 在一个有序的数组中,找到一个最大的比key小的数(即,最后一个比key小的数)    */    public static int getTheMaxLessKey(double[] a,int len,double key,int low,int high){        //1:如果最后一个数比key小        if(a[len-1]<key){            return len-1;        }        //2:如果第一个比key大        if(a[0]>key){            return -1;        }        if(low<len-1 && a[low]<key && a[high]>=key){            return low;        }        while(low<high-1){            int mid = low + (high-low)/2;            if(a[mid]>key){                high = mid;            }else{                low = mid;            }        }        return getTheMaxLessKey(a,len,key,low,high);    }}

 

再探二分查找