自己实现的BinarySearch

 解析详见:https://blog.csdn.net/qq_37768971/article/details/100168619

package IMUHERO;

public class BinarySearch {
    // BinarySearch : 1
    public int BS1(int [] arr,int val){
        int l = 0;
        int r = arr.length-1;
        while(l<=r){
            int mid = l+(r-l)/2;//防止溢出
            if(arr[mid]==val){
                return mid;
            }
            else if(val<arr[mid]){
                r = mid-1;
            }
            else if(val>arr[mid]){
                l = mid+1;
            }
        }
        return -1;
    }

    // BinarySearch : 2 左边界
    public int BS2(int[]arr,int val){
        int l = 0;
        int r = arr.length;//前闭后开
        while(l<r){
            int mid = l+(r-l)/2;
            if (arr[mid]==val) {
                r = mid;
            }
            else if(val<arr[mid]){
                r = mid;
            }
            else if(val>arr[mid]){
                l = mid+1;
            }
        }
        if (l == arr.length) return -1;//先判断val是不是大于所有的数
        return arr[l] == val ? (l) : -1;//再判断值是否相等
    }

    //BinarySearch : 3 右边界
    public int BS3(int [] arr,int val){
        int l = 0;
        int r = arr.length;//前闭后开
        while(l<r){
            int mid = l+(r-l)/2;
            if(arr[mid]==val){
                l = mid+1;
            }
            else if(val<arr[mid]){
                r = mid;
            }
            else if(val>arr[mid]){
                l = mid+1;
            }
        }
        if (l == 0) return -1;//先判断是否越界
        return arr[l-1] == val ? (l-1) : -1;//再判断值是否相等
    }

    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int [] arr = {1,2,3,4,5,6,7,8,9,10};
        int [] arr2 = {1,2,3,3,3,3,3,3,4,5,6,7,8,9,10};
        int [] arr3 = {1,2,3,3,3,3,3,3,4,5,6,7,8,9,10};
//        int res  = bs.BS1(arr,0);
        int res = bs.BS2(arr3,3);
        System.out.println(res);
    }
}

 

上一篇:<查找算法> 二分查找BinarySearch


下一篇:[转载] Java 中的binarySearch方法