4. Median of Two Sorted Arrays {

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

中位数是一个可将数值集合划分为相等的上下两部分的一个数值。 这道题就是找到可以将两个数组均分的值。一般解题思路是分治 Solution。

我这里把两个数组合并为一个排序后的数组，如果数组的长度是奇数，那么中间的数就是中位数，如果数组的长度是偶数，那么中位数就是位于中间的两个数的平均数。

My silly solution:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        l = sorted(nums1 + nums2)
        if len(l) % 2 == 1:
            return l[len(l) // 2]
        else:
            return (l[len(l) // 2 - 1] + l[len(l) // 2]) / 2

alvin19940815 official solution:

class Solution:
    def findMedianSortedArrays(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: float
        """
        # n>=m 
        m, n = len(A),len(B)
        if n<m:
            A, B, m, n = B, A, n, m
        
        imin, imax, halfLen = 0, m, (m+n+1)/2
        while(imin <= imax):
            i = int((imin+imax)/2)
            j = int(halfLen)-i
            if i > 0 and A[i-1] > B[j]:
                imax = i - 1
            elif i < m and A[i] < B[j-1]:
                imin = i + 1
            else:
                # i is perfect
                if i==0:
                    maxLeft = B[j-1]
                elif j==0:
                    maxLeft = A[i-1]
                else:
                    maxLeft = max(A[i-1], B[j-1])
                
                if (m+n) % 2 == 1:
                    return maxLeft
                else:
                    if i==m:
                        minRight = B[j]
                    elif j==n:
                        minRight = A[i]
                    else:
                        minRight = min(B[j],A[i])
                return (maxLeft+minRight)/2