当前位置：首页 > article >正文

【算法笔记】二分查找红蓝染色法

article 2024/11/15 11:18:39

二分查找红蓝染色法（感谢灵神）

这里是灵神的教学视频：二分查找红蓝染色法_哔哩哔哩_ bilibili

学了二分查找之后其实一直不是很理解，直到昨天看了灵神的讲解，有了全新的理解，有一种直冲天灵盖的感觉，写个笔记整理一下，感谢灵神

对于一个有序数组，我们如果想查找其中的某一个元素，我们可以通过从头遍历其中的所有元素，如果有匹配的元素，则返回元素的值，但是这种暴力解法不但没有利用有序数组这个特点，而且时间复杂度是O(n)，不是很有效率。

这个时候我们可以采用二分查找的方式：每次排除一半的元素，这样我们每查找一个元素的时候，他的时间复杂度就是O(logn)，要比暴力解法好很多。

二分查找中我们会涉及到一些变量，以及他们在每一轮循环中的变化情况：左右游标left、right，中间游标mid，以及我们要找的值target，其中左右游标用于在每次循环中缩小我们的查找区间并确定区间外数值的大小，mid游标用于与target值进行比较，辅助左右游标的具体移动情况。

闭区间[left, right]

下面我们介绍在闭区间[left, right]内查找的情况：

我们将left游标初始化为数组的起始下标0，right初始化为数组末尾的下标arr.length-1，mid指向左右游标的中间值left+(right - left)/2，这样我们每次就可以排除一半的数据，是最优解。

left+(right - left)/2这里为什么这样写，是因为防止在Java中直接进行left+right导致整型数字太大导致越界的情况
我们将 $< t a r g e t$ 的元素标记为红色， $\geq target$ 的元素标记为蓝色，但是我们要清楚，区间内的元素我们是不知道它们的颜色的，这点很重要！！假定我们现在要查找的数组为：[5,7,7,8,8,10]，target值为8，游标的位置如下图：
经过比较之后，我们发现mid指向的值为7，满足 $< t a r g e t$ 的条件，那么我们将left更新为mid+1，原有的元素变为如下的颜色：

这里为什么不更新为mid？？

这也是我一直不太清楚的一个点，现在我来试着说一下：因为我们选择的方式是在闭区间[left, right]内查找，所以我们要保证被比较过的元素在区间外面，没有比较过的元素在区间内部，而mid是我们比较的最后一个元素，那么我们只需要将游标更新为mid+1或者是mid-1就可以保证区间内的元素都是未经比较的，并且区间外的元素都是已经确定颜色的
继续进行比较，mid指向的值为8满足 $\geq target$ 的条件，此时我们不确定的区间也就是[left, mid-1]，所以我们更新右游标到mid-1的位置，保证区间外的元素都已经确定过：
继续进行比较，mid指向8，满足 $\geq target$ 条件，再次更新右游标到mid-1的位置：
到这个时候我们发现：整个数组已经全部染色，也就意味着我们确定了所有元素和目标元素的大小关系，我们要清楚一个关键点：right+1指向的元素一定是蓝色（ $\geq target$ ），left-1指向的元素一定是红色（ $< t a r g e t$ ），每次循环的过程中这个是不会变的，为了方便记忆灵神给这个关键点取名叫：循环不变量，我们清楚这一点之后，再去看那些循环条件或者是游标移动的位置，就很容易判断应该怎么写了。那么我们这里要找的元素8的位置也就找到了，直接返回下标right+1，或者是left就可以

我们看一下代码部分：

    public static int lower_bound(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){ // 闭区间内查找，当left > right的时候区间为空 
            int mid = left + (right -left) / 2;
            if (nums[mid] < target){
                left = mid + 1; // [mid + 1, right]是不确定的
            } else {
                right = mid - 1; // [left, mid - 1]是不确定的
            }
        }
        return left; // left所指向的位置就是元素出现的初始位置
    }

左闭右开区间[left, right)

左闭右开区间和闭区间的情况相似，我们需要修改右游标的初始位置为arr.length，因为右游标不再包括在区间内，也就是说再循环中[right, arr.length-1]的元素是确定好的；还需要修改的地方有右游标更新的位置，因为是开区间，所以直接移动到mid所在的位置就可以；最后是循环的终止条件，当left == right的时候区间为空，循环停止。下面是游标的初始位置：

在这里插入图片描述

那么我们开始循环：

mid所指向的值为8，满足条件 $\geq target$ ，我们将右游标移动至mid位置，并更新mid：
mid所指向的值为7，满足条件 $< t a r g e t$ ，我们将左游标移动到mid+1的位置，并更新mid：
mid所指向的值为7，满足条件 $< t a r g e t$ ，我们将左游标移动到mid+1的位置，并更新mid：
此时left == right，所有元素也都知道了大小，停止循环，并返回right。

代码部分

    public static int lower_bound(int[] nums, int target){
        int left = 0;
        int right = nums.length;
        while (left < right){ // 左闭右开区间内查找[left, right)
            int mid = left + (right -left) / 2;
            if (nums[mid] < target){
                left = mid + 1; // [mid + 1, right)是不确定的
            } else {
                right = mid; // [left, mid)是不确定的
            }
        }
        return right; // right所指向的位置就是元素出现的初始位置
    }

开区间(left, right)

原理差不多，就不一一画图了，需要修改：

左游标的初始位置：-1，因为是开区间上面已经解释过，我们需要保证区间内的元素是没有被确定的，而区间外的元素已经都被确定完毕
右游标的初始位置：arr.length
左游标更新的位置：mid
右游标更新的位置：mid
循环终止的条件：left + 1 == right，此时区间内已经没有元素

代码部分

    public static int lower_bound(int[] nums, int target){
        int left = -1;
        int right = nums.length;
        while (left + 1 < right){ // 开区间内查找(left, right)
            int mid = left + (right -left) / 2;
            if (nums[mid] < target){
                left = mid; // (mid, right)是不确定的
            } else {
                right = mid; // (left, mid)是不确定的
            }
            System.out.println(left + " " + right);
        }
        return right; // right所指向的位置就是元素出现的初始位置
    }