Mars's Blog

二分法总结

2021-07-07

阅读

基础分析

减治：每次排除不符合要求的元素，搜索空间持续减少

标准模版：(当目标元素有多个的时候)


在[l, r)上找目标元素

1
2
3
4
5
6
7
8
9
10
11
int l = 0, r = nums.size();
while (l < r) { //相等就退出
  int mid = l + (r - l) / 2; //也可以 long mid = (long)l + r >> 1
  if (target < nums[mid]) {
    r = mid; //说明答案在[l, mid)区间 注意r也是取不到的
  } else {
    l = mid + 1; //说明答案在(mid, r)，也就是[mid + 1, r)区间，根据数学归纳法可以排除掉A[mid]
  }// while的出口是大于target最小元素 查找成功不能提前终止。最后返回的l相当于upper_bound
  return --l; //此时 l == r，区间缩为一个点，l-1是不大于target的最大元素
  // 有多个命中元素，能返回秩最大值，查找失败，能返回失败的位置
}

最后将数组分为两个部分，左边满足<= target target > 右边

最后循环结束后，l是右半部分的第一个元素，l-1是左半部分最后一个元素

另一种写法：

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

两种写法的三点不同：r的初始值，while循环条件，r的移动规则（l都是mid+1）参考

核心是让本次循环和上一次循环的查找范围既不重复，也不遗漏

image-20210716100510835

网上总结关于二分的几种类型 https://www.cnblogs.com/grandyang/p/6854825.html

总结的很好：https://segmentfault.com/a/1190000016825704

基础题目

【LeetCode34】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> notFound({-1,-1});
        if (nums.size() == 0) return notFound;
        int start = binarySearch(nums, target - 1) + 1;
        int end = binarySearch(nums, target);
        cout << start << end;
        if (start <= end && nums[start] == target) return vector<int>({start, end}); //注意这里的start<=end,目的是排除当出现[2,2] 3 这样的用例时候的情况，这时候start = 2, end = 1
        return notFound;
    }
    int binarySearch(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (target < nums[mid]) r = mid;
            else l = mid + 1;
        }
        return --l;
    }
};

二段性

二段性理解

二分的本质不是单调性，而是二段性 满足二段性的特征就可以使用二分法，不一定需要严格符合二分的要求

二段性也不仅仅是满足/不满足进行二分，一定满足/不一定满足也可以二分

【LeetCode 152】

这道题的二段性的含义：在以mid为分割点的数组中，根据nums[mid+1]和nums[mid]的大小关系，可以确定一段必然有解，另一段可能有解，可能无解

因此选择一段进行二分，能保证区间内一定有峰值

简单的理解：如果nums[mid - 1] < nums[mid]，那么说明mid处可能为峰值，而mid-1处肯定不是峰值，因此在右半边继续找（需要注意因为要取到mid-1，所以l的初始值设为1）

严格证明：https://leetcode-cn.com/problems/find-peak-element/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-qva7v/

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

或者

由于下面要取mid+1，这种解法r最大能取到n-2

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

【LeetCode33】搜索旋转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (target == nums[mid]) return mid;
            //看mid分成的两部分那哪个是有序的
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) { //注意这里的等号
                    r = mid;
                } else l = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[r - 1]) { //注意这里的等号，还有r取不到
                    l = mid + 1;
                } else r = mid;
            }
        }
        return -1;
    }
};

需要明确一个规律，对于旋转数组，从任意一个地方切分，有一边的数组一定有序，另一边可能有序，可能无序

在每次二分中，先判断该区间是否有序，以及target是否在这段区间。然后可以在有序区间内二分查找，无序部分再进行切分，以此不断缩小搜索范围

其他思路：先判断target在左边还是右边，把另外一侧改为+Inf和-Inf。（主要是这个赋值的过程可以在二分的时候顺便完成的写法比较有趣）

四道旋转数组


【LeetCode 852】找出极值点 满足/不满足的二分

二段性：峰值左侧满足递增，右侧不满足，右侧满足递减，左侧不满足

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

如果是arr[mid]和arr[mid + 1]比较，最后返回l


【LeetCode4】

这道题和找出第k小的数字思路是一样的

递归方法：

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:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int l = nums1.size() + nums2.size();
        if (l % 2 == 0) return ( getKthElement(nums1, 0, nums1.size() - 1, nums2, 0, nums2.size() - 1, l / 2 ) + getKthElement(nums1, 0, nums1.size() - 1, nums2, 0, nums2.size() - 1, l / 2 - 1) ) / 2;
        else return getKthElement(nums1, 0, nums1.size() - 1, nums2, 0, nums2.size() - 1, l / 2 );
    }
    double getKthElement(vector<int>& nums1, int a, int b, vector<int>& nums2, int c, int d, int k) {
        if (b - a < 0) return nums2[k + c]; 
        if (d - c < 0) return nums1[k + a];
        if (k < 1) return min(nums1[a], nums2[c]);
        int i1 = (b + a) / 2, i2 = (d + c) / 2;
        int v1 = nums1[i1], v2 = nums2[i2];
        if ((i1 - a + i2 - c) < k) { //注意这里需要计算两个数组的前一半和为多少，这个需要与k比较
            if (v1 < v2) { //小的数字对应数组的前半部分不可能出现第k个数字，因此把1的前半段排除，搜索范围变小
                return getKthElement(nums1, i1 + 1, b, nums2, c, d, k - (i1 - a + 1));
            } else return getKthElement(nums1, a, b, nums2, i2 + 1, d, k - (i2 - c + 1));
        } else {
            if (v1 < v2) { //大数字对应数组的后半段不可能出现第k个数字
                return getKthElement(nums1, a, b, nums2, c, i2 - 1, k);
            } else return getKthElement(nums1, a , i1 - 1, nums2, c, d, k);
        }
    }
};

时间复杂度分析：每进行一次循环，就减少k/2个元素，所以时间复杂度为O(logK)，k = (m+n)/2，所以复杂度也就是O(log(m+n))

参考：

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2511/Intuitive-Python-O(log-(m%2Bn))-solution-by-kth-smallest-in-the-two-sorted-arrays-252ms

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

方法三-非递归方法


【LeetCode 352】

image-20211010193013470

相当于对于每个val，要找到离val最近的两个区间。(图片和下面代码的情况不对应)

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
class SummaryRanges {
private:
    map<int, int> intervals;

public:
    SummaryRanges() {}
    
    void addNum(int val) {
        // 找到 l1 最小的且满足 l1 > val 的区间 interval1 = [l1, r1]
        // 如果不存在这样的区间，interval1 为尾迭代器
        auto interval1 = intervals.upper_bound(val);
        // 找到 l0 最大的且满足 l0 <= val 的区间 interval0 = [l0, r0]
        // 在有序集合中，interval0 就是 interval1 的前一个区间
        // 如果不存在这样的区间，interval0 为尾迭代器
        auto interval0 = (interval1 == intervals.begin() ? intervals.end() : prev(interval1));

        if (interval0 != intervals.end() && interval0->first <= val && val <= interval0->second) {
            // 情况一
            return;
        }
        else {
            bool left_aside = (interval0 != intervals.end() && interval0->second + 1 == val);
            bool right_aside = (interval1 != intervals.end() && interval1->first - 1 == val);
            if (left_aside && right_aside) {
                // 情况四
                int left = interval0->first, right = interval1->second;
                intervals.erase(interval0);
                intervals.erase(interval1);
                intervals.emplace(left, right);
            }
            else if (left_aside) {
                // 情况二
                ++interval0->second;
            }
            else if (right_aside) {
                // 情况三
                int right = interval1->second;
                intervals.erase(interval1);
                intervals.emplace(val, right);
            }
            else {
                // 情况五
                intervals.emplace(val, val);
            }
        }
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for (const auto& [left, right]: intervals) {
            ans.push_back({left, right});
        }
        return ans;
    }
};

题目补充

【LeetCode 274】

【LeetCode 275】

【LeetCode 33】

Tags: 数据结构与算法
← P、NP、NPC、NP-Hard问题的区别 K8s 学习 →