acwing算法基础课笔记2-二分法

发表于 更新于 分类于 Artalk： loading...
二分

二分法的本质并不是单调性，而是二段性

在区间内找到一种“性质”，将整个区间一分为二，一半满足这种“性质”，一半不满足，寻找这种“性质”的边界点。

两种模版

实际使用中，应灵活运用

不推荐使用 左闭右闭的写法，仅在特殊情况下使用

第一种情况：判断是否满足红色区间性质时，upper_bound

小于等于某个数 targettarget 的最大值

如果满足（true），if (q[mid] <= target) l = mid;

而且 midmid 计算时记得加上1，即 mid=l+r+12mid=\frac{l+r+1}{2}

image-20210914205529899

第二种情况：判断是否满足绿色区间性质时，lower_bound

大于等于某个数 targettarget 的最小值

if (q[mid] >= target) r = mid

image-20210914210131500

第三种情况：判断序列中是否存在某个数 targettarget

  • 注意循环终止条件 while (l <= r)
  • 注意此时 区间端点 的设置
1
2
3
4
5
6
7
8
// 返回序号
int l = 0, r = q.length - 1;
while (l <= r) {
    int mid = l + r >> 1;
    if (q[mid] == target) return mid;
    else if (q[mid] < target) l = mid + 1;
    else r = mid - 1;
}

关于模版使用思考

  • 首先，由于二分的边界问题处理起来非常麻烦，记忆模板是避免边界处理出错

  • 具体使用时，要根据实际取值的合法性来判断更新后的区间端点。

    例如：q[mid]≤xq[mid] \le x ，则 xx 应该在 midmid 的右侧区间且可能取到 q[mid]q[mid] ，因此区间更新为 [mid,r][mid, r]

模板一中mid的更新为什么加1？

如果不加1

当本轮 left=right−1left = right{-}1 时，mid=left+right2=2left+12=leftmid = \frac{left+right}{2}=\frac{2left+1}{2}=left（向下取整），若判断成功， leftleft 更新为 mid=leftmid=left ，区间不变，会无限循环下去

举个🌰

若一个单调递增序列 q=[3,5]q= [3,5] ，目标是寻找小于等于 66 的最大元素，结果应该是 q[1]=5q[1] = 5 。

如果采用 mid=left+right2mid=\frac{left+right}{2} 模拟一下

1
2
3
4
5
6
7
8
round1: 
    l=0, r=1, mid=(0+1)/2=0;
    q[mid] <= 6 -->true
        l = mid = 0;
round2:
    l=0, r=1, mid=(0+1)/2=0;
    ……
产生死循环

拓展思考

以上述模板二为基础，看一道题

剑指 Offer II 068. 查找插入位置

题目简单描述：

给定一个排序数组（具备二段性的前提）和一个目标值 targettarget ，请在数组中找到等于目标值的元素，若不存在，则返回 targettarget 将会被插入的位置。

首先，这个问题跟 求大于等于target的最小值 的区别在于，给出的 targettarget 可能大于数组的任何一个元素。

  • 即 numsnums 不存在值等于目标的元素
  • 且 targettarget 要被插入最后一个元素之后

若直接采用模板二：

1
2
3
4
5
6
7
8
9
int n = nums.length;
int l = 0, r = n - 1;
// 以下计算的是 大于某个数的最小值的位置
while (l < r) {
    int mid = l + r >> 1;
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
}
return l;

对于测试用例：

1
2
index: 0,1,2,3
val:  [1,3,5,7] target=8

返回的答案是3，而8要插入的位置是4，错误，原因上面也提到了。

修改

1
2
3
4
5
6
7
8
9
10
while (l < r) {
    int mid = l + r >> 1;
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
}
// 
if (l == n - 1 && nums[l] < target) {
    return l + 1;
}
return l;

如果退出循环时，l=r=n-1并且nums[l]<target，即数组最大的元素也小于 targettarget ，那么返回l+1=n，一个对于数组来说非法的index。

进一步思考，是否可以省去最后的判断？

可以。

改变退出循环的方式

当前判断循环的条件是l < r，当l=r时退出。

若修改成：l <= r，当l=r时再进行一次判断，再退出循环。就可以包含上面提到的那种情况。

1
2
3
4
5
6
while (l <= r) {
    int mid = l + r >> 1;
    if (nums[mid] >= target) r = mid - 1;
    else l = mid + 1;
}
return l;

注意：

  • 此时l或者r可能非法

  • 搜索区间的更新方式也得改变，若还是 r = mid;当进行最后一次循环，l=r时，会产生死循环。

    • 改为r=mid-1
    • 这种方式跟r=mid的区别是什么？

  • 且此时，l = r + 1,返回值不可以随意

    • 本题所求目标：升序数组中，目标值插入的位置，逻辑上与求大于等于target的最小值一致，因此返回 left

举例子说明，若改成降序数组

[8,7,5,3,2] target = 6

1
2
3
4
5
6
7
8
9
10
int target = 6;
int l = 0, r = nums.length - 1;
while (l <= r) {
    int mid = l + r >> 1;
    if (nums[mid] >= target) l = mid + 1;
    else r = mid - 1;
}
int res = l; // 返回结果：2
int res = r; // 返回结果：1
System.out.println(res);
  1. 求6该插入的位置，应该插入到位置 22
  2. 数组中大于等于6的最小元素为7，位置是 11

结果很显然，最后，l=2,r=1。

这是这种写法，在对降序数组二分时的一种妙用，但是为避免使用出错，建议少用这种退出循环的方式。

小结一下：

无论用哪种结束循环方式，注意

  1. 保证区间是正常收缩的–>不要出现死循环
  2. 脑子要清楚退出循环的条件
  3. 建议继续采用左闭右开:l<r的方案

选模板的具体例子

acwing 789 数的范围

视频讲解

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
37
38
39
40
41
42
#include <iostream>

using namespace std;

const int N = 1e5+10;
int q[N];
int n, m;

int main(void){
    cin >> n >> m;
    for (int i = 0; i < n; ++i){
        cin >> q[i];
    }
    while (m -- ){
        int x;
        cin >> x;

        int l = 0, r = n - 1;
        while (l < r){ // 如果是 二分查找 的情况( q[mid] == target )，必须是 l <= r 得加“=”
            int mid = l + r >> 1;//先统一写上，之后再判断是否加1
            if (q[mid] >= x) r = mid; // 可能会取到mid值
            else l = mid + 1;
        }
        if (q[l] != x){
            cout << "-1 -1" << endl;
        }
        else{
            cout << l << " ";
            
            // 套用第一种模版，记得加1
            int l = 0, r = n - 1;
            while (l < r){
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
                //有个小规律，如果l=mid,r=mid-1;如果r=mid,l=mid+1
            }
            cout << l << endl;
        }
    }
    return 0;
}

做题时先把模版写上，不要加1先，然后判断具体是二分的哪个边界，true或者false的情况，每一次都选择答案所在的区间（可结合图形判断）

拓展例子

leetcode 162. 寻找峰值

由于nums[-1] = nums[n] = -∞向增大的方向一定能找到峰值。

就好比爬山，远方尽头确定是山脚，向上爬，无论如何，一定能爬到一个山峰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();

        int l = 0, r = n - 1;
        while (l < r){
            int mid = l + r + 1 >> 1; // l = mid情况，为防止无限循环记得“加1”
            if (nums[mid] > nums[mid - 1]) l = mid; // 向增大的方向去寻找，且可能取到mid，因此区间更新为[mid, r]
            else r = mid - 1;
        }
        return l;
    }
};

leetcode 4. 寻找两个正序数组的中位数

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        /* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
         * 这里的 "/" 表示整除
         * nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
         * nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
         * 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
         * 这样 pivot 本身最大也只能是第 k-1 小的元素
         * 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
         * 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
         * 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
         */

        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }
};

leetcode 33. 搜索旋转排序数组

思路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
class Solution {
    public int search(int[] q, int target) {
        int n = q.length;
        int l = 0, r = n - 1;
        if (n == 1) return q[0] == target ? 0 : -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (q[mid] == target) {
                return mid;
            }
            if (q[mid] >= q[l]) {
                // l~mid 有序 mid+1~r可能无序
                if (q[l] <= target && q[mid] > target) {
                    r = mid - 1;
                } else l = mid + 1;
            } else {
                if (q[r] >= target && q[mid] < target) {
                    l = mid + 1;
                } else r = mid - 1;
            }
        }
        return -1;
    }
}

思路2

此方法不好，如果旋转坐标 k=0k = 0 时间复杂度直接退化为 O(n)\Omicron(n)

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 search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        if (nums.size() == 1) return nums[0] == target ? 0 : -1;
        int l = 0, r = nums.size() - 1;

        while (r > 0 && nums[r] <= nums[l]){
            if (nums[r] == target) return r;
            r--;
        }
        while (l <= r){ // 等号是必须的，否则 如果结果在最后一次循环中时，会进不去
            // 例如 [1,3] 3
            int mid = l + r + 1 >> 1; // 在这个例题中 mid这加不加1 都可以；因为 l=mid+1 而不是l=mid
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return -1;
    }
};

81. 搜索旋转排序数组 II

元素可以重复

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 boolean search(int[] q, int target) {
        int n = q.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (q[mid] == target) return true;
            if (q[mid] == q[l] && q[mid] == q[r]) {
                l++;
                r--;
                continue;
            }
            if (q[mid] >= q[l]) {
                if (q[l] <= target && q[mid] > target) r = mid - 1;
                else l = mid + 1;
            } else {
                if (q[r] >= target && q[mid] < target) l = mid + 1;
                else r = mid - 1;
            }
        }
        return false;
    }
}

153. 寻找旋转排序数组中的最小值

注意：是寻找最小值。在确定有序区间时，好好思考一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findMin(int[] q) {
        int n = q.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (q[mid] < q[r]) { // 右半部分是有序的，则最小值一定在[l,mid]内 
                r = mid;
            } else {
                l = mid + 1; // 左半部分有序，并且此时q[mid] > q[r],右半部分存在小序列，最小值一定位于[mid+1,r]中
            }
        }
        return q[l];
    }
}

154. 寻找旋转排序数组中的最小值 II

元素可以重复

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findMin(int[] q) {
        int n = q.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1; //
            if (q[mid] < q[r]) r = mid;
            else if (q[mid] > q[r]) l = mid + 1;
            else r--;
        }
        return q[r];
    }
}

📔博文图谱

提及本博文的链接