二分搜索-第一个大于value的索引位置

若已知数组不存在value,想找第一个大于value的索引位置,左边界二分更合适

举例

左侧边界寻找value

public int fun(){
    int[] arr = new int[]{1,3,6,9,11,17};
    int n = arr.length;
    int left =0;
    int right = n-1;
    int value = 5;
    //int pos =0;
    while(left<=right){// 结束条件: left == right+1
        int mid = left+(right-left)/2;
        if(arr[mid]<value){
            //pos = mid;
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return left;
}

1. 比如找5,不存在就会返回大于5的第一个索引,left=2
2. 比如找6,存在返回6所在的索引,left=2
3. 比如找12,不存在就会返回大于12的第一个索引,left=5
4. 比如找17,存在返回17所在索引,left=5
5. 比如找18,不存在返回大于18所在的索引,left=6,已越界,注意手动判断

右侧边界寻找value

public int fun(){
    int[] arr = new int[]{1,3,6,9,11,17};
    int n = arr.length;
    int left =0;
    int right = n-1;
    int value = 5;
    //int pos =0;
    while(left<=right){// 结束条件: left == right+1
        int mid = left+(right-left)/2;
        if(arr[mid]<=value){
            //pos = mid;
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    return left-1; // left-1才是真实位置(因为left = mid+1;)
}

1. 比如找5,不存在就会返回大于5的第一个索引,left=2
2. 比如找6,存在返回6所在的索引,left=3,left-1=2
3. 比如找12,不存在就会返回大于12的第一个索引,left=5
4. 比如找17,存在返回17所在索引,left=6,left-1=5
5. 比如找18,不存在返回大于18所在的索引,left=6,已越界,注意手动判断,(返回值left-1未越界)

若已知数组不存在value,想找第一个大于value的索引位置,左边界二分更合适

二分搜索-第一个大于value的索引位置

原文：https://www.cnblogs.com/jobyterry/p/14613674.html