Description: Given 2 sorted array of size ‘n’ each, we have to  find the median  of the array formed(of length ‘2n’) if both arrays(of size ‘n’ each) were merged together.

Algorithm:

Firstly, lets define median. Median of odd number of sorted elements is the middle element. Median of even number of sorted elements is the average of the 2 middle elements

Eg: In an array of 4 elements, median is average of 2nd and 3rd element.

Lets consider a O(lgn) algorithm to solve the problem:

1.Find median of the arr1 and arr2, and store as med1 and med2 respectively.

2.

If the value of med1==med2, then return med1 as the required median.

Else If, med1>med2 , median must be present in:

-arr1[0…n/2]-   left half of arr1

-arr2[n/2…n-1]-   right half of arr2

Else ,(med1<med2), median must be present in:

-arr1[n/2..n-1]   -right half of arr2

-arr2[0…n/2]   -left half of arr1

3. Repeat steps 1 and 2 till the size of arr1 and arr2 goes down to 2.

4. The median is finally given by:

Median = (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1]))/2

Implementation using C:

/*The following function finds the median, if the 2 arrays are arr1 and arr2 each of size ‘n’.*/

int find_median(int arr1[], int arr2[], int n)

{

int med1,med2;

if (n == 1)

return (arr1[0] + arr2[0])/2;

if (n == 2)

return (max(arr1[0], arr2[0]) + min(arr1[1], arr2[1])) / 2;

/*med1 stores median of arr1*/

if (n%2 == 0)

med1= (arr1[n/2] + arr1[n/2-1])/2;

else

med1= arr1[n/2];

/*med2 stores median of arr2*/

if (n%2 == 0)

med2= (arr2[n/2] + arr2[n/2-1])/2;

else

med2= arr2[n/2];

/*if both medians are equal*/

if (med1 == med2)

return med1;

if (med1 < med2)

{

if (n % 2 == 0)

return find_median(arr1 + n/2 - 1, arr2, n - n/2 +1);

else

return find_median(arr1 + n/2, arr2, n - n/2);

}

else

{

if (n % 2 == 0)

return find_median(arr2 + n/2 - 1, arr1, n - n/2 + 1);

else

return find_median(arr2 + n/2, arr1, n - n/2);

}

}

int max(int a, int b)

{

return a > b? a : b;

}

int min(int a, int b)

{

return a > b? b : a;

}

Time Complexity:

O(lgn)

Go to top