求两个已排序数组的中位数

数组(s_1,s_2)，的中位数分别为(m_1,m_2)，数组长度为(n,m)（(n<=m)）

要求(O(log(n+m)))

1. 如果 (m_1==m_2)，合并后的数组的中位数就是(m_1或m_2)。（合并后(m_1,m_2)左右两边的数的个数相等）

2. 若(m_1<m_2)，则可以得到：合并后，在(m_1)左边的数的个数小于在(m_1)右边的数的个数（因为在(s_2)中，(m_1)出现的位置在(m_2)的左边）；同理，合并后，在(m_2)左边的数的个数大于在(m_2)右边的数的个数。
   又因为，中位数左边右边的数的个数相等，所以，合并后的中位数介于(m_1,m_2)之间。

3. 因为在中位数的左边剔除(x)个数，右边剔除(x)个数，剩下的数组的中位数还是原来的中位数。

基于上述规则，可以得到算法：

1. 计算数组的中位数(m_1,m_2)
2. 若 (m_1==m_2)，则返回(m_1)或(m_2)
3. 若(m_1>m_2)，则中位数存在于：$ s_1[0...|n/2|]$或 (s_2[|m/2|...m-1])
   令 $s_{1new}=s_1[0: |n/2| ],s_{2new}= s_2[ |n/2| :m-1 ] $
4. 若(m_2>m_1)，则中位数存在于：$ s_1[|n/2| ...n-1 ]$或 (s_2[ 0... |m/2|])
   令 $s_{1new}=s_1[ |n/2|:n-1 ],s_{2new}= s_2[0: m-1- |n/2| ] $
5. 对 (s_{1new}) ， (s_{2new})重复上诉操作， 求合并后的中位数。
6. 直到有一个数组的大小为0，对另一个数组求中位数。

def findMedianSortedArrays_2(self, nums1, nums2):
        l1=len(nums1)
        l2=len(nums2)

        if l1==0:
            return nums2[l2/2]
        if l2==0:
            return nums1[l1/2]      

        if l1==l2==1:
            if nums1[0]>nums2[0]:
                return nums1[0]
            else:
                return nums2[0]
        if l1==1:
            if nums1[0]>nums2[l2/2]:
                nums2=nums2[1:]
                return nums2[(len(nums2))/2]
            else:
                nums2=nums2[:l2-1]
                return nums2[(len(nums2))/2]
        if l2==1:
            if nums2[0]>nums1[(l1)/2]:
                nums1=nums1[1:]
                return nums1[(len(nums1))/2]
            else:
                nums1=nums1[:l1-1]
                return nums1[(len(nums1))/2]
        
        if l1>l2:
            return self.findMedianSortedArrays_2(nums2,nums1)

        m1=nums1[l1/2]
        m2=nums2[l2/2]
        if m1==m2:
            return m1
        if m1<m2:
            nums1=nums1[l1/2:]
            nums2=nums2[0:l2-(l1)/2]
        else:
            nums1=nums1[0:(l1+1)/2]
            nums2=nums2[l1/2:]
        print nums1,nums2
        return self.findMedianSortedArrays_2(nums1,nums2)

（参考）。