为什么在计算两个已排序数组的中值时使用较小的数组驱动二进制搜索？

Question

解决大小m和n的finding the median of two sorted arrays问题的常用算法是：

运行二进制搜索将 较小的 数组的 "a cut" 调整为两半。这样做时，我们调整 larger array 的切割以确保 both 数组前半部分的元素总数等于总数两个数组后半部分的元素数量，这是围绕中位数拆分两个数组的前提条件。
二分搜索将切割向左或向右移动，直到左半部分的所有元素 <= 右半部分的所有元素。
在过程结束时，我们可以通过对两个数组的切割边界上的元素进行基本比较，轻松计算出中位数。

虽然我对算法有较高的理解，但我不确定我是否理解为什么需要对较小的数组进行计算并调整较大的数组，而不是相反。

Here's一个解释算法的视频，但是作者并没有解释为什么我们使用较小的数组来驱动二进制搜索。

我还在下面添加了 Python 应该可以解决问题的代码，主要是为了使 post 独立，即使它没有很好的文档记录。

def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        ## Making sure that A refers to the smaller array
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

Answer 1

通过强制执行 m <= n，我们确保 i 和 j 始终是 非负数。

此外，在使用 i 和 j 时，我们能够减少 while 循环中的一些冗余边界检查。

以 while 循环中的第一个 if 条件为例，代码在访问 A[i] 之前检查 i < m，但为什么不也检查 j-1 >= 0 在访问 B[j-1] 之前？这是因为i落入[0,m]，而j = (m + n + 1) / 2 - i，所以当i最大时，j最小。当i < m，j = (m + n + 1)/2 - i > (m + n + 1)/2 - m = n/2 - m/2 + 1/2 >= 0。所以当i < m和j - 1 >= 0.

时j一定是正数

同理，while循环中的第二个if条件，当i > 0时，保证j小于n。

为了验证这个想法，您可以尝试删除顶部的大小检查和交换逻辑，并通过下面的示例输入运行，其中 A 比 B 长。

[1,2,3,4,6]
[5]

为什么在计算两个已排序数组的中值时使用较小的数组驱动二进制搜索？

Why have the smaller array drive binary search when computing the median of two sorted arrays?

python

algorithm

median