边界的二分搜索算法

用例：在递增数组arr中寻找大于等于target的最小元素索引

思路：利用双指针，采用二分法查找左边界

代码：

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

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4,6,7,8,8,8,8,9,10,16,19};
        int index = left_bound(arr, 8);
        System.out.println(index);
　　　　　//输出 5
    }

解读：

当目标元素target不存在数组arr中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读：

1、返回的这个值是arr中大于等于target的最小元素索引。

2、返回的这个值是target应该插入在arr中的索引位置。

3、返回的这个值是arr中小于target的元素个数。

比如在有序数组arr= [2,3,5,7]中搜索target = 4，搜索左边界的二分算法会返回 2，你带入上面的说法，都是对的。

所以以上三种解读都是等价的，可以根据具体题目场景灵活运用

边界的二分搜索算法

推荐阅读