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.

 
 
If video does not load, Click here
 
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