Median of two sorted arrays of equal length

Median of two sorted arrays

Given two sorted arrays, find the median of two sorted arrays of equal size.

Median of array of integers is middle of those integers if number of elements are odd and average of middle elements if number of elements is even.

For example if  A = {10,30,50, 60} and B = {30, 40, 100, 110} median will be (40+50)/2  = 45 as we if combine two sorted arrays C = {10,30,30,40,50,60,100,110} and since length is even, median will be (c[mid] + c[mid+1])/2. If the length of combined array is odd, then median will be c[mid].\

Method to find median of two sorted arrays

From definition, it follows that median of an array is either exactly middle element if number of elements is odd or average of two middle elements if number of elements is even. It also follows that if a[i] is median, following condition should be valid:  a[0] to a[median-1] <= a[median] <= a[median+1] to a[end]. It means that all elements on right side of the median should be greater and all the elements on left side should be smaller.  We will use this principle to arrive at median of two sorted arrays.

First, just find median of the array A and array B individually, Let us call them M1 and M2
If M1 = M2, then there will be equal number of elements on each side of M1 and M2 in both arrays (keep in mind that arrays are of equal size). Hence, we can return any one of the two as median.

Now, let’s take case where M1 < M2. It means that there are more elements on the right side of M1 in array A as compared to elements on right side of M2 in array B. So, search for median in right portion of array A and left portion of array B as shown in figure.

Similarly, if M2< M1, here are more elements on the right side of M2 in array B as compared to elements on right side of M1 in array A. Hence we should look for left part of array A and right part of array B.

median of two sorted arrays

Median of two sorted array algorithm

1. If length of both arrays is 1, take average and return the value.
2. If length of both arrays is 2, then return following value  (max(array1[0], array2[0]) + min(array1[1], array2[1]) )/2
3. If length is greater than 2, follow steps below
  3.a Find median of array A and array B individually. Let them be M1 and M2 
  3.b If M1 == M2 return M1 
  3.c If M1 < M2, follow step 1 onwards with array A[mid...N] and array  B[0, mid-1] 
  3.d If M2 < M1, follow step 1 onwards with array B[mid...N] and array B[0, mid-1]

Cool, since we have formalized the algorithm, we should code it now 🙂 There is one problem in the algorithm. Can you identify it? Yes if you run it for odd number of elements, it will fail, so let’s add conditions when N becomes odd, while dividing arrays. If N is odd, take middle element for next step where as for even N, leave middle element while going for the next step, why?

Median in two sorted arrays implementation

#include<stdio.h>
#define max(a,b) (a>b)?a:b
#define min(a,b) (a>b)?b:a
 
int findMedianUtil(int a[], int n){
    if(n%2 ==0)
      return (a[n/2] + a[n/2+1])/2;
    else
      return a[n/2];
}
 
int findMedian(int a[], int b[], int n){
    //Case where there is one element in each array
    if(n == 1)
        return (a[0] + b[0])/2;
 
    //Case where size of both array is 2
    if(n == 2)
        return (max(a[0], b[0]) + min(a[1],b[1]))/2;
 
    int medianA = findMedianUtil(a,n);
    int medianB = findMedianUtil(b,n);
 
    //If both medians are equal
    if(medianA == medianB)
        return medianA;
    // else search in appropriate parts of array
    else if(medianA < medianB){
        if(n%2 ==0){
            /* If no. of elements are even, then do not include 
            middle element in next step */
            return findMedian(a+n/2-1, b, n-n/2);
        }
        else{
            /* If no. of elements are odd, then include middle element 
            in next step */
            return findMedian(a+n/2, b, n-n/2);
        }
    }
    else if(medianA > medianB){
    	if(n%2 ==0)
    	    return findMedian(b+n/2-1, a, n-n/2);
        else
            return findMedian(b+n/2, a, n-n/2);
    }
    return -1;
}
int main(){
 
	int a[] = {10,30,40,50,60};
	int b[] = {30,50,100,110, 200};
	int size  = sizeof(a)/sizeof(a[0]);
 
	int median;
	median = findMedian(a,b, size);
	printf("\n Median of two sorted array is : %d", median);
 
	return 0;
}
Let us understand execution trace using an example.
Array A  = {10,30,50, 60, 70, 100} 
Array B = {30, 40, 100, 110, 130, 150}. Size = 6
Median is 65

To start with, find median of two arrays individually.

Call find_median_1(A,6)

Median of array A  (m1) = A[mid] + A [mid+1] /2 = ( 50 + 60 )/2 = 55.

Call find_median_1(B,6)

Median of array 2 (m2)  = B [mid] + B [mid+1] /2 = ( 100 + 110 )/2 = 105.

Since median of array A is not equal to median of array B, compare two medians m1 and m2. Since m2 > m1, second condition is true. As per algorithm, look left part of array B and right part of array A.

Call find_median (a+n/2-1, b, n -n/2); find_median(A+3-1, B, 3)

Now arrays to be looked in are:  A’ = {60,70, 100} and B’ = {30, 40,100}.

Call find_median_1(A,6) m1'= 70;
Call find_median_1(B,6) m2' = 40.

Now, m1′ > m2′.  So, look in left part of A and right part of B, and since length of arrays is odd, hence include mid element.

Call find_median (b+n/2, a, n -n/2); find_median(B'+1, A', 2 )

A” = {60,70} and B” ={40,100}

Since size of arrays is now 2, terminal condition is reached.

(max(a[0], b[0]) + min(a[1],b[1]))/2.

Max (A[0], B[0]) = 60 and min (A[1], B[1]) = 70. Median will be  (60 + 70)/2 = 65.

Complexity of algorithm to find median of two equal sized sorted arrays will be O(log n)
There are couple of other ways in which we can find out median of two sorted arrays. I will put them in sometime. If you have available code, you can send me mail or write in comments. I will add it to the post. Thanks!