// A divide and conquer based efficient solution to find median
// of two sorted arrays of same size.
#include<bits/stdc++.h>
using namespace std;

int median(int [], int); /* to get median of a sorted array */

/* This function returns median of arr1[] and arr2[].
Assumptions in this function:
a. Both ar1[] and ar2[] are sorted arrays
b. Both have n elements */
int getMedian(int arr1[], int arr2[], int n)
{
/* return -1 for invalid input */
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 m1 = median(arr1, n); /* get the median of the first array */
int m2 = median(arr2, 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 will be in arr1[m1....] and arr2[....m2] */
if (m1 < m2)
{
if (n % 2 == 0)
return getMedian(arr1 + n/2 - 1, arr2, n - n/2 +1);
return getMedian(arr1 + n/2, arr2, n - n/2);
}

/* if at all m1 > m2 then-> median must be in in arr1[....m1] and
arr2[m2...] */
if (n % 2 == 0)
return getMedian(arr2 + n/2 - 1, arr1, n - n/2 + 1);
return getMedian(arr2 + n/2, arr1, n - n/2);
}

/* Function to get median of a sorted array */
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 array1[] = {1, 2, 3, 6};
int array2[] = {4, 6, 8, 10};
int n1 = sizeof(array1)/sizeof(array1[0]);//to find the size of the array1
int n2 = sizeof(array2)/sizeof(array2[0]);//to find the sizr of array2
if (n1 == n2)
printf("Median is %d", getMedian(array1, array2, n1));
else
printf("Doesn't work for arrays of unequal size");
return 0;
}