等长排序数组的中位数

Question

我正在尝试找到两个相同长度的排序数组的中位数，为此我正在使用分而治之算法。但是我的代码 returns None 而不是一个值这是查找单个数组中位数的代码：

def getmedian(li):
    x = len(li)
    if x%2 == 0:
        return (li[x//2] + li[(x//2)-1])/2
    else:
        return li[(len(li)-1)//2]

然后我对两个数组使用以下函数：

def TwoList(list1,list2):
    if len(list1) == 1:
        return (list1[0] + list2[0])/2
    elif len(list2)== 2:
        return (max(list1[0],list2[0]) + min(list2[1], list1[1]))/2
    else:
        #pdb.set_trace()
        x = getmedian(list1)
        y = getmedian(list2)
        if x == y:
            return x
        elif x > y:
            if len(list1)%2==0:
                TwoList(list1[:len(list1)//2], list2[len(list1)//2:])
            else:
                TwoList(list1[:len(list1)//2+1], list2[len(list1)//2:])
        else:
            if len(list1)%2==0:
                TwoList(list1[len(list1)//2:], list2[:len(list1)//2])
            else:
                TwoList(list1[len(list1)//2:], list2[:len(list1)//2+1])

Answer 1

看起来你做得对，除了在 TwoList 递归调用中返回值。
请参阅下面的代码，在必须 return 值的地方进行注释。

def getmedian(li):
    x = len(li)
    if x%2 == 0:
        return (li[x//2] + li[(x//2)-1])/2
    else:
        return li[(len(li)-1)//2]

def TwoList(list1,list2):
    if len(list1) == 1:
        return (list1[0] + list2[0])/2
    elif len(list2)== 2:
        return (max(list1[0],list2[0]) + min(list2[1], list1[1]))/2
    else:
        #pdb.set_trace()
        x = getmedian(list1)
        y = getmedian(list2)
        if x == y:
            return x
        elif x > y:
            if len(list1)%2==0:
                return TwoList(list1[:len(list1)//2], list2[len(list1)//2:]) # return value
            else:
                return TwoList(list1[:len(list1)//2+1], list2[len(list1)//2:]) # return value
        else:
            if len(list1)%2==0:
                return TwoList(list1[len(list1)//2:], list2[:len(list1)//2]) # return value
            else:
                return TwoList(list1[len(list1)//2:], list2[:len(list1)//2+1]) # return value

print(TwoList([1,2,3,4],[5,6,7,8]))

等长排序数组的中位数

Median of sorted arrays of equal length

python-3.x

median

divide-and-conquer