二分法中的边界问题

最近面试训练了一些算法题目，发现自己对二分法的边界问题有点混乱，在这里总结记录一下。二分法的边界问题一般和left和right的取值有关，一般可以选择左闭右闭和左闭右开。下面根据这两种情况进行讨论。

左闭右闭方法

左闭右闭方法即left指向数组中第一个元素(0)，right指向数组中最后一个元素(len-1)。对于这种情况，我们首先考虑while循环中的条件，因为left和right都在数组范围内，因此left<=right也是需要进入循环并判断的。

public int binarySearch1NonRecursive(int[] arr, int target){
        int left=0;
        int right=arr.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;//既可以防止溢出，也可将mid始终指向偏left一侧（向下取整）
            if(arr[mid]>target){
                right=mid-1;
                continue;
            }else if(arr[mid]<target){
                left=mid+1;
                continue;
            }
            return mid;
        }
        return -1;
    }
}

注意 int mid=left+(right-left)/2 这句代码，这句代码其实很巧妙，首先可以保证两数相加除2永远不会发生越界问题，其次还可以保证在查找区间长度为偶数时，二分过程中其mid始终指向中间偏左的元素（向下取整）。
下面再给一个递归的解决方法

public int binarySearch1ByRecursive(int[] arr, int target, int left, int right){
        if(left>right || arr==null){
            return -1;
        }
        int mid=left+(right-left)/2;
        if(arr[mid]>target){
            return binarySearch1ByRecursive(arr, target, left, mid-1);
        }else if(arr[mid]<target){
            return binarySearch1ByRecursive(arr, target, mid+1, right);
        }else {
            return mid;
        }
}

左闭右开

左闭右开即left指向0，right指向数组的长度(arr.length)。和上面一样，首先想到right是始终不在数组的索引值范围内的。因此，while中的循环条件变为left<right。另一个问题，我们在循环过程中选择向上还是向下取整呢？答案是选择向下取整，因为我们使用了左闭右开的方法，向上取整可能出现越界问题。如何在循环过程中始终让mid一直向下取整呢？参考上文的公式：mid=left+(right-1-left)/2即可。

public int binarySearch2NonRecursive(int[] arr, int target){
        int left=0;
        int right=arr.length;
        while (left<right){
            int mid=left+(right-left-1)/2;
            if(arr[mid]>target){
                right=mid;//注意此处的right更新方式与上面的不同
                continue;
            }else if(arr[mid]<target){
                left=mid+1;
                continue;
            }
            return mid;
        }
        return -1;
    }

同样的，也给出一个递归写法

public int binarySearch2ByRecursive(int[] arr, int target, int left, int right){
        if(left>=right || arr==null || arr.length==0){
            return -1;
        }
        int mid=left+(right-left-1)/2;
        if(arr[mid]>target){
            return binarySearch2ByRecursive(arr, target, left, mid);
        }else if(arr[mid]<target){
            return binarySearch2ByRecursive(arr, target, mid+1, right);
        }
        return mid;
}