Day65 | 灵神 | 二分查找：红蓝染色法

灵神讲解的非常好建议大家去听听灵神的，二分查找就是常忘常学常新，我之前学过很多次二分，但这次还是有新的理解，我把可能比较难理解的点写到了下面，大家没看懂视频的地方可以看看我写的

当然主要的其实是check函数，在本题中就是大于等于target这个条件，估计灵神下个视频会讲吧

二分查找 红蓝染色法【基础算法精讲 04】_哔哩哔哩_bilibili

34.在数组排序中查找元素的第一个和最后一个位置

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

视频中的可能的难点

0.区间的定义

我觉得这个很重要，不管是定义左闭右开还是左闭右闭，在区间内的数字就是我们接下来要去判断的数字，看看是否满足条件

而区间外的数字都是已经判断过的不满足条件的

1.关于while中什么时候有等号，什么时候没等号的问题

循环条件中的l<r或者l<=r有没有等号看的是当l==r的时候[l,r]这个区间是否有数字

如果是左闭右闭，那当然有意义，两个指向同一个数字，比如[2,2]

如果是左闭右开，那当然就是空的了，比如[2,2)，在数学上这是个空集

如果是左开右开那更不必说了

2.循环不变量

而灵神说的循环不变量就是指的是循环过程中要保证区间左闭右闭这个性质不发生改变，不可以原来是左闭右闭，后面直接换成左闭右开了，那样就会出错

3.关于if中 什么时候是mid-1，mid+1什么时候是mid

看你选定的区间的l和r在mid+1或者mid-1或者mid，什么时候可以保持循环不变量，那就是什么

举例

1.比如我选定的是左闭右开区间[l,r)，那我每次更新l的时候l就是mid+1，因为当l==mid时nums[mid]可以取到并且不符合条件，那就直接等于mid+1

而更新r的时候呢？r==mid时nums[mid]其实没有意义，因为r这边是开区间，我们取不到r，所以更新r的时候必须是r=mid，才可以继续保证[l,r)是一个开区间

2.选定的如果是左闭右闭区间[l,r]，那更新l就是mid+1，更新r就是mid-1，因为不管是l==mid时还是r==mid都是有意义的，而且只有这样才能满足更新后的区间继续保持[l,r]这个闭区间

4.关于 大于、小于、大于等于、小于等于这四种情况的举例说明

关于大于、小于、大于等于、小于等于这四个情况的说明，如果大家没听懂灵神说的可以看看我写的

大于和大于等于找的是左边界，小于和小于等于找的是右边界

我就拿题目中的例子作为说明

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

target=8，令x=8

大于等于x就是我们原来找的，直接就可以找到下标为3的8，即左边界

大于x可以看做大于等于x+1，即在这个数组里面大于8就相当于大于等于9，直接找到的就是10

小于x可以看做 找到大于等于x的那个数的下标之后再减1，即(>=x)-1，在数组中就是要找小于8的数，而我们找到下标为3的第一个8，再用下标3-1=2，那就是小于8的数，也就是7，但这个是右边界

在本题中可以直接用(>=9)-1这样的方式直接找到8的右边界，即4

小于等于x可以看做 找到大于x的那个数的下标之后再-1，即(>x)-1，在本题中找到的是下标为5的10，再减去1得到的是下标为4的8，即找到的是右边界，并且这个直接就找到了目标值8的右边界

完整代码

大家记住一个写法就行，我一般常用的是左闭右开的写法，因为很多容器和算法都是左闭右开这个区间，有些习惯吧算是

可能遇到的不清楚的我都写了注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int lower_bound(vector<int>& nums, int target)
    {
        int l=0,r=nums.size();
        while(l<r)//l==r时没有意义，不写等号
        {
            int mid=l+(r-l)/2;//防止溢出
            if(nums[mid]>=target)
                r=mid;//左闭右开，右边是开的 不需要写mid-1
            else
                l=mid+1;
        }
        return l;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        //找左边界
        int first=lower_bound(nums,target);
        //这两种情况说明数组里面没target
        if(first==nums.size()||nums[first]!= target)
            return {-1,-1};
        //找右边界，刚刚说了找右边界肯定就是小于或者小于等于的情况，这两种情况可以由找左边的情况互换过来
        //即去找>=target+1的的左边界，在第一个例子中就是大于等于9，找到后就是右边界的下一位置，那么再减去1，那就是最后的答案
        int last=lower_bound(nums,target+1)-1;
        return {first,last};
    }
};

笔者自己学过的二分代码的思路

找左右边界，左边界找法和灵神相同，右边界找法就是我下面写的这种，也就是nums[mid]<=target时去更新l

其实找左边界就是根据条件从右往左收缩，找右边界就是从左往右收缩

然而不管是左边界还是右边界，终止条件都是l==r，也就是最后的时候l和r是相等的，返回哪个都行

最后还要注意一点是我用的是左闭右开区间，最后找到的右边界取不到，所以记得看看题目要求，如果找的是target这个数字的右边界记得要-1，要是算个数啥的一般不用减

顺带一提这个和stl算法中的二分查找函数的结果相同，即左边界是第一个target，右边界是最后一个target+1的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int lower_bound(vector<int>& nums, int target)
    {
        int l=0,r=nums.size();
        while(l<r)
        {
            int mid=l+(r-l)/2;//防止溢出
            if(nums[mid]>=target)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
    int upper_bound(vector<int>& nums, int target)
    {
        int l=0,r=nums.size();
        while(l<r)
        {
            int mid=l+(r-l)/2;//防止溢出
            if(nums[mid]<=target)
                l=mid+1;
            else
                r=mid;
        }
        return l;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int first=lower_bound(nums,target);
        if(first==nums.size()||nums[first]!= target)
            return {-1,-1};
        int last=upper_bound(nums,target)-1;
        return {first,last};
    }
};

2529.正整数和负整数的最大计数

2529. 正整数和负整数的最大计数 - 力扣（LeetCode）

做一道题练练手，检验一下自己的学习成果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lower_bound(vector<int>&nums,int target)
    {
        int l=0,r=nums.size();
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>=target)
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
    int maximumCount(vector<int>& nums) {
        //找0的左边界 这是负整数的右边界 并且取不到，给出答案 因为下标本身比第几个数字小1，所以不用做别的处理，直接就是负整数的个数
        int first=lower_bound(nums,0);
        //找1的左边界 这是正整数的左边界
        int last=lower_bound(nums,0+1);
        return first>nums.size()-last?first:nums.size()-last;
    }
};

当然，直接遍历也可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maximumCount(vector<int> &nums) {
        int neg = 0, pos = 0;
        for (int x : nums) {
            if (x < 0) {
                neg++;
            } else if (x > 0) {
                pos++;
            }
        }
        return max(neg, pos);
    }
};