**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