python解决从有序数组中寻找中位数

如果给定两个长度分别是m和n的有序数组array1和array2，需要对这两个有序数组找出其中的中位数，需要保证时间复杂度是O(long(min(m,n))，空间复杂度是O(1)。如下例子：

添加图片注释，不超过 140 字（可选）

添加图片注释，不超过 140 字（可选）

对于该例子的中位数是由(3+5)/2得到的。

添加图片注释，不超过 140 字（可选）

对于此给定的数组的两个数组合并长度是奇数，所以中位数是中间位置的4。

对于该问题的解决思路，要寻找两个有序数组的中位数，假设两个数组的长度分别是m和n，第一张工方法是最简单直接的，也就是另外开辟一块m+n大小的空间，将这两个数组合二为一然后重新进行排序，根据合并之后的数组取中位数就十分简单了，但是该方法简单，时间复杂度是最高的，实现的代码如下：

def findMedian(self,nums,nums2):
    nums3 = nums2+nums
    nums3.sort()
    return (nums3[len(nums3)//2]+nums3[len(nums3)-1]//2)/2

但是该方法是不符合问题的限制条件的，对于问题所要求的时间复杂度是对数形式，只有不断地进行二分才有可能出现对数时间复杂度的情况，所以这里考虑采用二分法，再对二分之后的数组进行分治处理。

这里两个有序数组，分别找到两个数组array1和array2的中位数，分别是median1和median2，若果median1小于median2，则median1左侧的所有元素均小于它，这些元素不可能是中位数，可以截去头部到median2之前的所有元素，长度为p2，而median2右侧的所有元素均大于它，越接近尾部元素最大，也不可能是中位数，截去尾部长度为p2的部分，然后对这两个数组被截去后的剩余部分执行同样的操作，当其中较短数组长度为2的时候，较长数组长度如果大于4，则可以再截取其中间长度为3或者4的部分，这时候两个数组剩余部分长度是常数级别的，可以直接排序取中位数。python实现的代码如下：

class Solution:
    def findmedian(self, array1, array2):
        len1=len(array1)
        len2=len(array2)
        if len1>len2:
            return self.findmedian(array2,array1)
        if len1<=2:
            if len2>4:
                p1=math.ceil(len2/2)-2
                array2=array2[p1:-p1]
            nums=array1+array2
            nums.sort()
            return self.getmediannum(nums)
        p2=math.ceil(len1/2)-1
        if self.getmediannum(array1)<self.getmediannum(array2):
            return self.findmedian(array1[p2:],array2[:-p2])
        else:
            return self.findmedian(array1[:-p2],array2[p2:])  
#定义一个取数组中位数的函数       
    def getmediannum(self,nums):
        return (nums[len(nums)//2]+nums[(len(nums)-1)//2])/2

此方法可以满足时间复杂度和空间复杂度。