CareerCup

This problem is from Cormen chap 9 - prob 9.3-8
Let X[1..n] and Y[1..n] be two sorted arrays each containing n numbers already in sorted order.
Algorithm is as follows

TWO-ARRAY-MEDIAN(X,Y)
n = length[X] // n also equals length[Y]
median = FIND-MEDIAN(X,Y,n,1,n)
if (median == NOT-FOUND)
      then median = FIND-MEDIAN(Y,X,n,1,n)
return median

FIND-MEDIAN(A,B,n,low,high)
 if(low > high)
     return NOT-FOUND
 else
    {
      k = (low+high)/2
      if(k == n && A[n] <= B[1]
            return A[n]
      else if(k<n && B[n-k] <= A[k] <= B[n-k+1]
            return A[k]
      else if(A[k]> B[n-k+1]
           return FIND-MEDIAN(A,B,n,low,k-1)
      else
          return FIND-MEDIAN(A,B,n,k+1,high)
    }

int find_median(int *a, int a_lower, int a_upper, int *b, int b_lower, int b_upper, int size)
{
if(a_lower == a_upper && b_lower == b_upper)
{
// we have only one element in both the array
return (a[a_upper] < b[b_upper])?a[a_upper]:b[b_upper];
}

int median_a = a[a_lower+size/2];
int median_b = b[b_lower+size/2];

// Case 1 : If both the medians are equal
if(median_a == median_b)
return median_a;
//
// Case 2 : if m1>m2 then median must exist in arr1[a1, a2,…m1] and arr2[b1, b2,…m2….bM]

if(median_a > median_b)
return find_median(a, a_lower, a_upper-size/2, b, b_lower+size/2, b_upper,(size+1)/2 );
else if (median_a < median_b)
return find_median(a, a_lower+(size/2), a_upper, b, b_lower, b_upper-size/2, (size+1)/2);

return -1;

@Ganesh

I think your code will not work for

A[]={1,3,5,17,19}
B[]={10,11,12,13,14}

O(log n)....compare the middle elements of the arrays....depending on which element is bigger....take the upper half of one array n lower half of the other....go on till we have 1 element.....thts the median....in case of even number of elements...there can be 2 medians....

a median is described as the number separating the higher half of a sample from the lower half.

if the length of the array is odd, the centre element is the median. If it is even, the two centre elements are the medians!

Right?

A related problem i feel find the median of BST in O(logn)

kjflkdjsfkdjfsjdkdlsjfdsjj

Say A= {1 2 4 6 8 9}
B= {2 5 7 10 11}

Median = {1 2 2 4 5 6 7 8 9 10 11} = 6

int nMedianIndex = (6 + 5) / 2 = 6 or ( 5 in case of zero based index) This means that the median should be the 5th index if all are in one array, sorted.
int nCountindex = 0

do{
1) Compare each element of the two arrays. if element in first array > elelmet in second array, increase second array index
2) Compare each element of the two arrays. if element in second array > elelmet in first array, increase first array index
3) Compare each element of the two arrays. if element in first array = elelmet in second array, increase both indices
4) nCountIndex+=1;
} while (nCountIndex <=nMedianIndex)

return nCOutnIndex.

Complexity: O(n) & O(1)