Median of two sorted arrays.

Problem statement: There are 2 sorted arrays A and B of size n each. What is the fastest way to find the median of the elements of both the array.

Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.
The median of a finite list of numbers can be found by sprting and picking the middle one.

Median of N elements in an array of elements [0..N-1] is

Solution 1: O(n)
Simple and slow, Merge the array and apply above formula.

Solution 2: O(log (n))
By comparing the medians of 2 array.

#include<stdio.h>
#define MAX(a , b) (a>b)?a:b
#define MIN(a , b) (a<b)?a:b
int median(int [], int); /* to get median of a sorted array */
int get_median(int array_1[], int array_2[], int n)
{
	int m1; /* For median of array_1 */
	int m2; /* For median of array_2 */
	if (n <= 0)
	return -1;
	if (n == 1)
	return (array_1[0] + array_2[0])/2;
	if (n == 2)
	return (MAX(array_1[0], array_2[0]) + MIN(array_1[1], array_2[1])) / 2;
	m1 = median(array_1, n); /* get the median of the first array */
	m2 = median(array_2, n); /* get the median of the second array */
	/* If medians are equal then return either m1 or m2 */
	if (m1 == m2)
	return m1;
	/* if m1 < m2 then median must exist in array_1[m1....] and array_2[....m2] */
	if (m1 < m2)
	{
		if (n % 2 == 0)
			return get_median(array_1 + n/2 - 1, array_2, n - n/2 +1);
		else
			return get_median(array_1 + n/2, array_2, n - n/2);
	}
	/* if m1 > m2 then median must exist in array_1[....m1] and array_2[m2...] */
	else
	{
		if (n % 2 == 0)
			return get_median(array_2 + n/2 - 1, array_1, n - n/2 + 1);
		else
			return get_median(array_2 + n/2, array_1, n - n/2);
	}
}

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 main()
{
	int array_1[] = {1, 2, 3, 7, 8, 10, 12};
	int array_2[] = {4, 7, 8, 10, 15, 30, 32};
	int n1 = sizeof(array_1)/sizeof(array_1[0]);
	printf("Median is %d", get_median(array_1, array_2, n1));
	return 0;
}

P.S. You can also use binary search approach.
P.P.S. Your task becomes much much easier if all the elements of Array 1 is smaller than Array 2 😉

Please suggest more optimized approach if possible. 🙂