Wny在计算两个排序数组的中值时，是否使用较小的数组驱动二进制搜索？

Question

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

1. 运行二进制搜索，将较小的数组的“切块”调整为两半。在执行此操作时，我们调整较大数组的剖切，以确保两个数组前半部分的元素总数等于两个数组后半部分的元素总数，这是围绕中位数拆分两个数组的先决条件
2. 二进制搜索将剪切向左或向右移动，直到左半部分上的所有元素<；=右半部分上的所有元素
3. 在程序结束时，我们可以通过对两个阵列切割边界上的元素进行基本比较，轻松计算中值

虽然我从较高的层次上理解了算法，但我不确定我是否理解为什么需要在较小的数组上进行计算，并调整较大的数组，而不是相反

---

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

我还包括了下面的Python代码，这些代码应该是用来解决这个问题的，主要是为了使文章自包含，即使它没有很好的文档记录

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，但为什么不在访问B[j-1]之前检查j-1 >= 0？这是因为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。所以j在i < m和j - 1 >= 0时必须为正

类似地，在while循环中的第二个if条件中，当i > 0，j被保证小于n

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

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