二分查找

二分查找 #

1、有序数组,查找一个数搜索一个数,如果存在,返回其索引,否则返回 -1。 #

int binarySearch(vector<int>& nums, int target) {    int left = 0;
    int right = nums.size() - 1; // 注意
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        else if(nums[mid] == target)
            return mid;
    }
    return -1;
}

1、为什么 while 循环的条件中是 <=,而不是 <? #

答:因为初始化right的赋值是nums.length - 1,每次进行搜索的区间,相当于两端都闭区间[left, right]。while 循环什么时候应该终止?搜索区间为空的时候应该终止,意味着你没得找了,就等于没找到嘛。

while(left <= right)的终止条件是left == right + 1,写成区间的形式就是[right + 1, right],这时候区间为空,所以这时候 while 循环终止是正确的,直接返回 -1 即可。

while(left < right)的终止条件是left == right,写成区间的形式就是[right, right],或者带个具体的数字进去[2, 2],这时候区间非空,还有一个数 2,但此时 while 循环终止了。也就是说这区间[2, 2]被漏掉了,索引 2 没有被搜索,如果这时候直接返回 -1 就是错误的。

2、为什么left = mid + 1,right = mid - 1?我看有的代码是right = mid或者left = mid,没有这些加加减减,到底怎么回事,怎么判断? #

答:本算法的搜索区间是两端都闭的,即[left, right]。那么当我们发现索引mid不是要找的target时,下一步应该去搜索哪里呢?当然是去搜索[left, mid-1]或者[mid+1, right]对不对?因为mid已经搜索过,应该从搜索区间中去除。

3、此算法有什么缺陷? #

答:比如说给你有序数组nums = [1,2,2,2,3],target为 2,此算法返回的索引是 2,没错。但是如果我想得到target的左侧边界,即索引 1,或者我想得到target的右侧边界,即索引 3,这样的话此算法是无法处理的。这样的需求很常见,你也许会说,找到一个 target,然后向左或向右线性搜索不行吗?可以,但是不好,因为这样难以保证二分查找对数级的复杂度了。

2、有序数组,寻找左侧边界 #

int left_bound(int[] nums, int target) {    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else{
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.size() || nums[left] != target)
        return -1;
    return left;
}

1、为什么 while 中是<而不是<=? #

答:每次循环的「搜索区间」是[left, right)左闭右开。 while(left < right)终止的条件是left == right,此时搜索区间[left, left)为空,所以可以正确终止。

2、如果nums中不存在target这个值,怎么办? #

左侧边界的特殊含义:nums中小于 target 的元素有 left 个。

3、为什么left = mid + 1,right = mid?和之前的算法不一样? #

答:这个很好解释,因为我们的「搜索区间」是[left, right)左闭右开,所以当nums[mid]被检测之后,下一步的搜索区间应该去掉mid分割成两个区间,即[left, mid)或[mid + 1, right)。

4、为什么该算法能够搜索左侧边界? #

答:关键在于对于nums[mid] == target这种情况的处理。找到 target 时不要立即返回,而是缩小「搜索区间」的上界right,在区间[left, mid)中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。

3、有序数组,寻找右侧边界 #

int right_bound(int[] nums, int target) {    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}