二分算法的变种----查找递增可重复数组边界

public class test {
    //数组长度a,b,c为8,d为7；
    static int[] a = {3,5,8,8,8,9,9,10};
    static int[] b = {8,8,8,8,8,8,8,8};
    static int[] c = {0,0,0,0,0,0,0,0};
    static int[] d = {0,0,0,0,0,0,0};
    public static void main(String[] args) {
        int target = 0;
        System.out.println("左边索引为：" + foundleft(target,d));
        System.out.println("右边索引为：" + foundright(target,d));
    }

    //要求时间复杂度为：log2n  --->  使用二分查找；
    //基本想法：不管是否找到 target值，都移动左右索引，直到左右索引重合；最后输出条件：索引重合&&索引处的数据为target；

    private static int foundleft(int target,int[] arr) {
        int left = 0,right = arr.length - 1;
        while (left != right){
            int mid = (left + right) / 2;
            if (target <= arr[mid]){
                right = mid;
            } else{
                left = mid;
            }
            if (right - left == 1 && arr[left] == target)
                return left;
            if(right - left == 1 && arr[right] == target)
                return right;
            if (right - left == 1)
                return -1;
        }
        return left;
    }

    private static int foundright(int target,int[] arr) {
        int left = 0,right = arr.length - 1;
        while (left != right){
            int mid = (left + right) / 2;
            if (target < arr[mid]){
                right = mid;
            } else{
                left = mid;
            }
            if(right - left == 1 && arr[right] == target)
                return right;
            if (right - left == 1 && arr[left] == target)
                return left;
            if (right - left == 1)
                return -1;
        }
        return right;
    }
}

上面的注释中说到基本想法：等到索引重合无法实现，不论是奇数个还是偶数个查找，最终都会以左右索引差1结束。因为当right - left==1时，mid与right或left永远相等。

可以进一步优化代码和效率：（主要是方法那部分）

private static int foundleft(int target,int[] arr) {
        int left = 0,right = arr.length - 1;
        while (right - left > 1){
            int mid = (left + right) / 2;
            if (target <= arr[mid]){
                right = mid;
            } else{
                left = mid;
            }
        }
        if (arr[left] == target)
            return left;
        if(arr[right] == target)
            return right;
        return -1;
    }

    private static int foundright(int target,int[] arr) {
        int left = 0,right = arr.length - 1;
        while (right - left > 1){
            int mid = (left + right) / 2;
            if (target < arr[mid]){
                right = mid;
            } else{
                left = mid;
            }
        }
        if(arr[right] == target)
            return right;
        if (arr[left] == target)
            return left;
        return -1;
    }
}