Median of Two Sorted Arrays

06/24/2016 Array Divide and Conquer Binary Search

Question

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 .

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

Result: Accepted Time: 24ms

int imin(int a, int b)
{
    return a > b ? b : a;
}

int find_kth(int* a, int na, int* b, int nb,int k)
{
    if(na < nb)
        return find_kth(b,nb,a,na,k);
    if(nb == 0)
        return a[k-1];
    if(k == 1)
        return imin(a[0],b[0]);
    int pb = imin(k / 2, nb), pa = k - pb;
    if(a[pa - 1] == b[pb - 1])
        return a[pa - 1];
    else if(a[pa - 1] > b[pb - 1])
        return find_kth(a,na,b+pb,nb - pb,k - pb);
    else
        return find_kth(a+pa,na-pa,b,na,k-pa);
}

double findMedianSortedArrays(int* a, int na, int* b, int nb) {
    const int cnt = na + nb;
    if(cnt & 1)
        return find_kth(a,na,b,nb,(cnt+1)/2);
    return (find_kth(a,na,b,nb,cnt/2) + find_kth(a,na,b,nb,cnt/2+1))*0.5;
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: