Median of two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Solution

(1) Solution one , merge A and B into a new array and find the mid one kth, time is O(m+n)

(2) findKth

核心解法，就是比较两个数组的mid=k/2 -1, 谁小谁出列排除，但是如果A数组或者B数组，不够k/2 - 1 直接取数组的最后一个值进行比较。

class Solution:
    """
    @param A: An integer array.
    @param B: An integer array.
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        # write your code here
        n = len(A) + len(B)
        if n % 2 == 1:
            return self.findKth(A, B, n / 2 + 1)
        else:
            start = self.findKth(A, B, n / 2)
            end = self.findKth(A, B, n / 2 + 1 )
            mid = (start + end) / 2.0
            return mid

    def findKth(self, A, B, k):
        if len(A) == 0:
            return B[k - 1]
        if len(B) == 0:
            return A[k - 1]
        if k == 1:
            return min(A[0], B[0])
        # A or B less than k /2 means, A + B < 2/k so the kth should be in the one which is more than k/2    
        a = A[k / 2 - 1] if len(A) >= k / 2 else A[len(A) - 1]
        b = B[k / 2 - 1] if len(B) >= k / 2 else B[len(B) - 1]

        if a < b:
            return self.findKth(A[k / 2:], B, k - k / 2)
        else:
            return self.findKth(A, B[k / 2:], k - k / 2)