寒夜雨 主页归档标签读书影音游戏关于我资源搜集友链我的个人维基
Algorithms【2】：二分法
|
字数总计: 2.9k|阅读时长: 10 分钟

前言

分治法的通用步骤是：划分-求解-合并。将一个比较大的问题拆分成若干小问题，然后分别求解。分治法和动态规划的区别在于，分治法通常求解子问题之间彼此独立的场景，而动态规划用于求解子问题之间不独立的场景。这一区别将在动态规划一节中阐述。

分治法最常用的算法为二分法，也就是将问题分割为两个子问题，分别求解之后进行合并。

简单的例子：归并排序

用Python语言的归并排序实现如下所示：

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
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    divide_point = len(arr) // 2
    left = merge_sort(arr[:divide_point])
    right = merge_sort(arr[divide_point:])
    return merge(left, right)

def merge(left_arr, right_arr):
    result = []
    while len(left_arr) > 0 and len(right_arr) > 0:
        if left_arr[0] < right_arr[0]:
            result.append(left_arr.pop(0))
        else:
            result.append(right_arr.pop(0))
    while len(left_arr) > 0:
        result.append(left_arr.pop(0))
    while len(right_arr) > 0:
        result.append(right_arr.pop(0))
    return result

if __name__ == "__main__":
    arr1 = [1,2,3,4,5,6,7,8,9]
    arr2 = [9,8,7,6,5,4,3,2,1]
    arr3 = [1,3,5,7,9,2,4,6,8]

    print(merge_sort(arr1))
    print(merge_sort(arr2))
    print(merge_sort(arr3))

其中，merge_sort函数控制着整个排序过程，在这个过程中，首先将待排序的list对半分，分为两个部分，分别对左右两个部分排序后，再进行合并操作。合并操作的过程受merge函数控制。

如您所见，分治算法的划分过程，是将大问题（排序整个list）分割为不相关的小问题（排序左右两个list，且这两个排序过程彼此独立），求解的过程，是处理最小的、能够直接解决的小问题（当分割的list中只有一个元素）的过程，合并的过程，则是对子问题进行综合处理，得到大问题的解（将两个排好序的list合并）。

“在写分治算法的过程时，不要过度关心分解该怎么做，而是关心该如何分解”。这是一个非常微妙的描述，更具体来说，就是不要关心分解之后的问题经历了什么，而是要关心如何分割问题，分治算法的关键在于最小问题的处理方法以及合并的方法。

简单的例子：二分查找

基础二分查找

一个更能分治法的算法是二分查找，二分查找的目的是在给定一个排好序的序列中，寻找到想要的值的下标。这个算法的复杂度达到了惊人的$\Theta(\log n)$。这个算法通过对半划分，每次查找能筛选掉一半的候选项，所以这个算法的复杂度实际上是$\Theta(\log_2n)$。一个Python实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    target = 4
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            print(mid)
            break
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

这个函数的划分方式不如归并排序那样清晰，不过我们能够从循环中能看出来：每次搜索，首先判断数列中间的值，如果这个值比目标值大，那么就表明，中间这个值在目标值的右边，就搜索中间值左边的子数列；如果这个值比目标值小，那么就表明，中间这个值在目标值的左边，就搜索中间值右边的子数列。

这里，值得注意的是while left <= right这句代码。这一行代码中的=体现了分治算法中，考虑“最小问题的处理方法”的重要性。添加了一个等号，就表明数列没有元素时，也要进行判断，这个时候判断的是left和right同时指向的位置的值。如果不加=，那么算法需要被改写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    target = 4
    left = 0
    right = len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target:
            print(mid)
            break
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # New Stuff. You can also replace left with right.
    if arr[left] == target:
        print(left)

这个时候，最后需要判断left和right指向的值的大小。

简单的变体：算术平方根的计算

这个问题可以通过Leetcode 69访问。这个问题的一个AC解是：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = (left + right) // 2
            mid_res = mid * mid
            if mid_res < x:
                left = mid + 1
            elif mid_res > x:
                right = mid - 1
            else:
                return mid
        return left - 1

这个算法的重点是最后一行的left - 1是什么意思，更大一点说，二分查找最后左右指针指向的位置代表什么。其实，最后一行也可以换为return right，当我们找不到目标值时，left和right会指向离目标值最近的点，left会指向比这个值大的点，而right会指向比这个值小的点。

我们做一个不那么严谨的数学推导，来证明最后一次二分运算时，就是left==right的情况。假设原来的序列长度是$k$，序列从1开始计数，那么每次筛选掉的元素有多少？通过上面的例子我们知道，中间点的坐标是$[\frac{k}{2}]$，中间点及其某一侧的点全被舍弃，那么舍弃的长度$\text{DiscardLength}$以及余下的长度$\text{LeftLength}$就是：
$$
\text{DiscardLength}(k)=[\frac{k+1}{2}]
$$

$$
\text{LeftLength}(k)=k-\text{DiscardLength}(k)
$$

当然，如果$k$是奇数，那么有$\text{DiscardLength}(k)=\frac{k+1}{2}$，可以推得：
$$
\text{LeftLength}(k)=2n+1-\frac{2n+2}{2}=n
$$
如果是偶数，那么有$\text{DiscardLength}(k)=\frac{k}{2}$，可以推得：
$$
\text{LeftLength}(k)=2n-n=n
$$
易知$n=[\frac{k}{2}]$，我们知道$[\frac{k}{2}]\leq \frac{k}{2}$，那么最后的长度总不会大于$\frac{k}{2^n}$，而我们知道：
$$
\lim_{n\to\infty}\frac{k}{2^n}=0
$$
那么，最后的结果就是，left和right指向同一个地方（它们之间有0个元素）。在这个时候，再经历一次二分运算，中间值便是这两个指针指向的位置，这个时候，如果中间值比目标值小，那么左指针右移，符合我们的预期，反之就右指针左移。最终都是left会指向比这个值大的点，而right会指向比这个值小的点。

那么回看问题，我们的目标是求得目标数字算术平方根的整数部分，显然要找小于这个点的值。就是右指针指向的位置。

中等的变体：有规律而非排好序的二分查找

这个问题可以通过Leetcode 162访问。这个问题的一个AC解是：

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
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if mid == 0:
                if nums[mid] > nums[mid+1]:
                    return mid
                else:
                    left = mid + 1
            elif mid == len(nums) - 1:
                if nums[mid] > nums[mid-1]:
                    return mid
                else:
                    right = mid - 1
            else:
                if nums[mid-1] < nums[mid] and nums[mid+1] < nums[mid]:
                    return mid
                elif nums[mid-1] > nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

这道题中，数列并没有排好序，但是这不影响我们用二分查找，这便是二分查找的一种推广——只要问题中能够筛选一半的数据，就可以使用二分查找。

中等的例子：最邻近点距

这个问题的描述很简单：在一个二维平面上，有$n$个点，寻找到欧几里得距离最近的两个点。如果直接穷举，那么复杂度将是$O(n\times (n-1)!)$。第一个$n$是计算每个点对欧几里得距离的开销，后面一项则是每个点的计算次数。但是，通过分治算法，我们可以把复杂度降到$O(n\log n)$。

既然说到分治法，那么第一步肯定就是分割，首先将所有点按照横坐标/纵坐标排序，然后按照中间横坐标点进行分割，分割为左右两边，一直分割到最后只有两个点。这一步的复杂度受排序复杂度为主导，而排序的复杂度显然是$O(n\log n)$。

求解过程，就是求左右两个子集内部的最邻近点距，记作$d_1,d_2$，其中假设$d_1>d_2$，令$d=\min(d_1,d_2)$。

合并过程则tricky一些，通过划分-求解过程，我们求到了两个子集内部的最邻近点距，但是两个子集之间呢？我们以划分点为中心，左右各划出$d$的空间。对于纵坐标，我们只考虑划分点上下各$d$的空间，这是一个正方形的空间，边长为$d$。

这个空间内，最大有6个点。我们可以将这个空间分割为若干底边为$\frac{d}{2}$，高边为$\frac{2d}{3}$的矩形，每个矩形里只能有一个点，否则根据容斥原理，$d=\frac{5d}{6}$。

到此，这个算法分析完了，其复杂度为$O(n\log n)$。

中等的例子：求两个排好序的数列的中位数

这个问题可以通过Leetcode 4访问。这个问题的一个AC解是：

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
class Solution:
    def solve(self, nums1, nums2, target_idx):
        left1, right1 = 0, len(nums1) - 1
        left2, right2 = 0, len(nums2) - 1
        while True:
            if left1 > right1:
                return nums2[target_idx - left1]
            if left2 > right2:
                return nums1[target_idx - left2]

            mid_idx1, mid_idx2 = (left1 + right1) // 2, (left2 + right2) // 2
            mid_val1, mid_val2 = nums1[mid_idx1], nums2[mid_idx2]
            if mid_idx1 + mid_idx2 < target_idx:
                if mid_val1 >= mid_val2:
                    left2 = mid_idx2 + 1
                elif mid_val1 < mid_val2:
                    left1 = mid_idx1 + 1
            else:
                if mid_val1 >= mid_val2:
                    right1 = mid_idx1 - 1
                else:
                    right2 = mid_idx2 - 1

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        mid_val = (len(nums1) + len(nums2)) // 2
        if (len(nums1) + len(nums2)) % 2 == 1:
            return self.solve(nums1, nums2, mid_val)
        else:
            return (self.solve(nums1, nums2, mid_val) + self.solve(nums1, nums2, mid_val-1)) / 2.

这道题的重点在于分割的方式，对于总长的奇偶性的分割，这里不再赘述。主要来看一下solve函数的解法。

为了求解中位数，那么我们筛去的长度$\text{FilteredLength}$必然为：
$$
\text{FilteredLength}=\frac{\text{ArrayLength}_1+\text{ArrayLength}_2}{2}
$$
其中，$\text{ArrayLength}_1$代表nums1的元素个数。那么，这种情况，我们就可以应用二分法，每次迭代来合理地筛选掉一部分元素。当然可以通过在两个数列内分别二分，最后合并的方法来求解。

首先，我们可以考虑一下两个数列到底有哪些可能性：

  1. nums1的最大值小于nums2的最小值，即$[1,2,3]$和$[4,5,6]$。
  2. nums1和nums2有一部分交集，比如$[1,3,5]$和$[2,4,6]$。
  3. nums1的最小值大于nums2的最大值，即$[4,5,6]$和$[1,2,3]$。

我们首先来考虑情况1和3，并且两个数列之间的长度差异很大，那么中位数必然落在某一个数列的中间。假设我们已经知道了合并方法，那么在二分的时候，长度小的数列，其必然会被完全筛选掉，而筛选掉的情况便是左指针大于右指针的值，那么这个时候，只需要考虑一个数列即可。

那么我们来讨论最为困难的情况——两个数列需要合并的情况。这个情况又可以分为两类，即筛选多于整体一半和筛选少于整体一半的情况。这里的筛选是指筛选掉小于中位数的数字。如果筛选多了，就要调节右指针，让整体往值较小的方向靠近；如果筛选少了，就要调节左指针，让整体往值较大的方向靠近。值得注意的是，如果筛选掉的值正正好好，那么我们需要调节右指针，避免出现筛选过量的情况。

文章作者: 幻
文章链接: https://www.coderlock.site/2025/08/20/Algorithms【2】：分治法/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 寒夜雨！
Algorithms