2n个数的中位数问题_python_算法与数据结构

问题 ：
对于两个长度均为n的已排序的序列,确定这两个序列的2n个元素的中位数。

解决此问题的算法思想：
设两个长度为n的数列分别为x[ 0 : n -1]和y[ 0 : n -1],分别找出这两个数列的中位数x[i]和
y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索范围,然后再分别取
两个子数列的中位数再比较,再减少搜索范围,继续下去直到找到最后结果。采用分治法来做，时间复杂度:O(lgn).

   网址：中位数问题 对这个问题进行了较为深入的阐述。下面给出了Python的代码实现：

def fidMid(cx1,cx2):
    size = len(cx1)
    midSize = size //2
    if (size ==1 ):
        if(cx1[0] >=cx2[0]):
            return cx2[0]
        else:
            return cx1[0]
    if(cx1[midSize] <=cx2[midSize]):
        for i in range(0, midSize):
            cx1.pop(0)
            cx2.pop()
    else:
        for i in range(0, midSize):
            cx2.pop(0)
            cx1.pop()
    return fidMid(cx1, cx2)
if '__name__ = __main__' :
     x=[10, 15, 16, 19, 24]
     y=[11, 17, 18, 20, 23]
     print(fidMid(x, y))

复杂性分析：采用了二分查找的办法，树的节点个数为2n，因此算法的时间复杂度为= .