Sunday, February 9, 2014

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)).

Solution:
When met with time of log(n), it occurs to us that binary search should be a good candidate. 
revised binary search, divide both array into two parts. ---> find the kth element


public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int aLen = A.length;
        int bLen = B.length;
        if((aLen + bLen) % 2 != 0)
            return getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2+1);
        else
            return (getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2) + 
                   getKthElement(A, 0, aLen-1, B, 0, bLen-1, (aLen+bLen)/2+1)) * 0.5;
    }
    public double getKthElement(int[] A, int aBeg, int aEnd, int[] B, int bBeg, int bEnd, int k){ // k >= 1
        if(aBeg > aEnd) return B[bBeg + k-1];
        if(bBeg > bEnd) return A[aBeg + k-1];
        int aMid = (aEnd + aBeg) / 2;
        int bMid = (bEnd + bBeg) / 2;
        int len = (aMid - aBeg + 1) + (bMid - bBeg + 1);
        if(len > k){ // drop a bigger section
            if(A[aMid] < B[bMid]){
                return getKthElement(A, aBeg, aEnd, B, bBeg, bMid-1, k);
            }
            else{
                return getKthElement(A, aBeg, aMid-1, B, bBeg, bEnd, k);
            }
        }
        else{ // drop a smaller section
            if(A[aMid] < B[bMid]){
                return getKthElement(A, aMid+1, aEnd, B, bBeg, bEnd, k-(aMid-aBeg+1));
            }
            else{
                return getKthElement(A, aBeg, aEnd, B, bMid+1, bEnd, k-(bMid-bBeg+1));
            }
        }
    }
}

No comments:

Post a Comment