Saturday, February 21, 2015

Median of two sorted array.

Problem: There are two sorted arrays of size n each. Write an algorithm to find the median of the array obtained after merging the given two arrays.

Algorithm:
1) Calculate the medians med1 and med2 of the input arrays arr1[]
   and arr2[].
2) If med1 and med2 both are equal then return med1.
3) If med1 is greater than med2, then median is present in one
    of the below two subarrays.
      a)  From first element of arr1 to med1.
      b)  From med2 to last element of arr2.
4) If med2 is greater than med1, then median is present in one  
    of the below two subarrays.
      a)  From med1 to last element of arr1.
      b)  From first element of arr2 to med2.
5) Repeat the above process until size of both the subarrays becomes 2.
6) If size of the two arrays is 2 then use following formula to get the median:
       Median = (MAX(arr1[0], arr2[0]) + MIN(arr1[1], arr2[1]))/2

Implementation:
inline int MAX(int i, int j)
{
       return i > j ? i : j;
}

inline int MIN(int i, int j)
{
       return i < j ? i : j;
}

int median(int *arr, int n)
{
    if(n % 2 == 0)
         return (arr[n/2] + arr[n/2 - 1]) / 2;
    else
        return arr[n/2];
}

int getMedian(int *arr1, int *arr2, int n)
{
    if(n <= 0)
         return -1;
    if(n == 1)
         return (arr1[0] + arr2[0]) / 2;
    if(n == 2)
         return (MAX(arr1[0], arr2[0]) + MIN(arr1[1], arr2[1])) / 2;
    int med1 = median(arr1, n);
    int med2 = median(arr2, n);
   
    if(med1 == med2)
          return med1;
    if(med1 < med2)
    {
          if(n % 2 == 0)
               return getMedian(arr1 + n/2 - 1, arr2, n - n/2 + 1);
          else
               return getMedian(arr1 + n/2, arr2, n - n/2);
    }
    else
    {
        if(n % 2 == 0)
             return getMedian(arr1, arr2 + n/2 - 1, n - n/2 + 1);
        else
             return getMedian(arr1, arr2 + n/2, n - n/2);
    }
}

Time Complexity: O(logn)

No comments:

Post a Comment