【常见面试算法】二分法-不但可知具体的位置，也可查左右边界

【转载】本文为CSDN博主「我还年轻我很平凡」的原创文章
原文链接：https://blog.csdn.net/weixin_43784989/article/details/98229031

1、简单二分

那么接下来，我们先来看看二分查找的最常用的场景：查一个有序数组的某一数字是否存在(下标)：

//target意为目标数字
public int searchNum(int target){
int l = 0;
int r = nums.length - 1;
while (l <= r) {
    int mid = l + ((r - l) >> 1);
    if(nums[mid] == target){
        return mid;
    } else if (target < nums[mid]){
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}
return -1;//表示没有找到该数字
}

2、 复杂二分查找(查找左边界)

假设有一个有序数组{1,2,2,2,3}，这个时候让你查找target=2的边界，计算之后返回的结果肯定是是按下标处理过后：（1,3）
这个时候你可能会觉得，这有啥？费这么大劲？用什么二分法？沙13吧？当然，这个数组长度非常短，费不着用什么二分法，一次遍历就可以解决。那么如果数组很长尼？O(N)和O(logN)你倾向与哪个？答案就在下面：配合着图和代码你就知道了：

//target=2
public int findLeftBound(int target){
    int l = 0;
    int r = nums.length; //这里需要注意
    while (l < r){
        int mid = l + ((r - l) >> 1);
        if (nums[mid] >= target){  //这里需要注意
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

至于为什么会是这样？这其实就和作用域一样，左闭右开/左闭右闭，自己画个图就明白了

3、复杂二分查找(查找右边界)

其实和查找左边界没什么多大区别，只是在返回的时候需要注意，因为作用域是[L,R),所以在返回有右边界的时候-1再返回：

public int findRightBound(int target){
    int l = 0;
    int r = nums.length;
    while (l < r){
        int mid = l + ((r - l) >> 1);
        if (nums[mid] > target){
            r = mid;
        } else{
            l= mid + 1;
        }
    }
    return r - 1;
}