leetcode Question 50: Median of Two Sorted Arrays

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. The overall run time complexity should be O(log (m+n)).

Analysis:

Note that the definition of the Median:
(1) If the size of the sequence N is odd: N/2+1th element is median.
(1) If the size of the sequence N is even:  average of the N/2th and N/2+1th element is median.

So in this problem, median of the two sorted arrays is the (m+n)/2+1 th element (if m+n is odd), the average of (m+n)/2 th and (m+n)/2+1 th  (if m+n is even).
E.g.,  [1,2,3],[5,6,7], the median is (3+5)/2 = 4.0.
          [1,2,3,4], [1,3,5,7,9], the median is 3.

Our task becomes finding the Kth (K or K+1, K=(m+n)/2) number in two sorted arrays, in O(log(m+n)) time constraint (what's in your mind to see log? Yes, binary search).

Similar to but slight different from binary search, we still divide K into two halves each time. Two pointers are used for each array, so that we can compare which side is smaller (?A[pa]>B[pb]).
E.g., A = [1,3,5,7,9]  B = [2,4,8,10,12,14,16,18]. K=(5+8) /2= 6.

pa = K/2 = 3;
pb = K-pa = 3;
         pa
A[1,3,5,7,9]
         pb
B[2,4,8,10,12,14,16,18]

if (A[pa]<B[pb]), which means the elements from A[0] to A[pa] must exist in the first Kth elements.
The next step now becomes finding the (K-pa) th (equals to K/2) element in the array A[pa:end] and B[].  This procedure can be viewed as "cutting" K/2 elements from the "smaller" array, and continue find the other K/2 th elements from the "bigger" array and the array after the cut. Note that smaller and bigger here is the comparison of the last elements.

if (A[pa]>B[pb]), the same procedure is applied but we "cut" the B array.

In this way, every time we have "cut" K/2 elements from one of the arrays, the next time is to cut (K/2) /2 elements from the new arrays, until:
(1) K=1, the smaller one from A[0] and B[0] is the "Kth element".
(2) One of the array meets the end. Then just return the current Kth element from the other array.



Misc. In C++, the array pointer is relative easy, (1) the array alone name represents the pointer pointed to the first element of the array, and pointer+n points to the nth element of the array. e.g.
double [3] arr = {1.0,2.0,3.0};
double *p = arr;        // *p=arr[0]=1.0;
p=p+2;                     //*p=arr[2]=3.0;

Code(C++):

class Solution {
public:

    double fms(int A[], int m, int B[], int n, int k){
        
        if (m>n) {return fms(B,n,A,m,k);}
        
        if (m==0) { return B[k-1];}
        if (k==1) { return min(A[0],B[0]);}
        int pa = min(k/2,m);
        int pb = k-pa;
        if (A[pa-1]<=B[pb-1]) {return fms(A+pa,m-pa,B,n,k-pa);}
        return fms(A,m,B+pb,n-pb,k-pb);
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int total = m + n;
        if(total%2==1){
            return fms(A,m,B,n,total/2+1);
        }else{
            return (fms(A,m,B,n,total/2)+fms(A,m,B,n,total/2+1))/2;
        }
        
    }
};

Code(Python):

class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        if (len(A) + len(B)) % 2 == 0:
            return (self.fms(A, B, (len(A) + len(B))/2) + self.fms(A, B, (len(A) + len(B))/2 + 1))/2.0
        else:
            return self.fms(A, B, (len(A) + len(B))/2 + 1)
    
    def fms(self, A, B, k):
        if len(A) > len(B):
            return self.fms(B, A, k)
        else:
            if len(A) == 0:
                return B[k-1]
            if k == 1:
                return min(A[0], B[0])
            pa = min(k/2, len(A))
            pb = k - pa
            if A[pa-1] <= B[pb-1]:
                return self.fms(A[pa::], B, k-pa)
            else:
                return self.fms(A, B[pb::], k-pb)