使用分而治之和递归找到两个排序数组的中位数

Question

我试图找到两个不同大小的排序数组的中位数，使用递归以“分而治之”的方式。输入是两个排序数组，输出是这两个排序数组的中位数。

我试图不合并这些数组，然后找到中位数。我想做的只是直接返回中位数。

示例：

鉴于我有
• ar1 = [1, 2, 3, 4, 12]

   和 

  ar2 = [0, 7, 8, 11]

  ，中位数是 4

鉴于我有
• ar1 = [1, 2, 3, 4, 12]

   和 

  ar2 = [0]

  ，中位数是 2

我知道解决问题的可能性有很多，但我想使用递归和分而治之的方式来编写代码。

此外，虽然我的代码适用于某些情况，但它不适用于其中一个数组的大小为 1 的情况。我很乐意就如何修复此基本情况的代码提供建议。我可以看到问题来自代码中的前两个“if”。但如果我删除它们，我将不会返回递归树的叶子，因此它不适用于其他情况。

import math

def medianOfTwo(L1, L2, l1, h1, l2, h2):

  if (h1 == l1): return L1[l1]
  if (h2 == l2): return L2[l2]

  medL1 = math.floor((l1+h1)/2)
  medL2 = math.floor((l2+h2)/2)


  if(L1[medL1] == L2[medL2]):
    return L1[medL1]
  

  if(L1[medL1] < L2[medL2]):
    return medianOfTwo(L1, L2, medL1, h1, l2, medL2)
  else:
    return medianOfTwo(L1, L2, l1, medL1, medL2, h2)


#ar1 = [1, 2, 3, 4, 12] 
#ar2 = [0, 7, 8, 11] 

ar1 = [1, 2, 3, 4] 
#ar2 = [7, 8, 11, 12]
ar2 = [0]

print(medianOfTwo(ar1, ar2, 0, len(ar1)-1, 0, len(ar2)-1))

Answer 1

这是一个递归分而治之的方法，在每个级别从两个数组的组合中删除最小值和最大值。一旦剩下两个或更少的值，中值结果就是剩余值中较小的一个（如果您想要平均值，请将

min(arr1 + arr2)

 替换为 

return sum(arr1 + arr2)/2

）。

def median(arr1, arr2):
    if len(arr1 + arr2) <= 2:
        return min(arr1 + arr2)
    if len(arr1) == 0:
        return median(arr1, arr2[1:-1])
    elif len(arr2) == 0:
        return median(arr1[1:-1], arr2)
    if arr1[0] < arr2[0]:
        if arr1[-1] > arr2[-1]:
            return median(arr1[1:-1], arr2)
        else:
            return median(arr1[1:len(arr1)+1], arr2[:-1])
    else:
        if arr2[-1] > arr1[-1]:
            return median(arr1, arr2[1:-1])
        else:
            return median(arr1[:-1], arr2[1:len(arr2)+1])

median([1, 2, 3, 4, 12], [0, 7, 8, 11])
median([1, 2, 3, 4], [0])
median([10], [0, 5, 9, 12])

输出：

4
2
9