# Program to find Median of two sorted arrays of equal size in C

## Median of two sorted arrays of equal size in C

Here, in this page we will discuss the program to find median of two sorted arrays of equal size in C++ programming language. We are given with two arrays say arr1[] and arr2[] of the same size say n . We need to find the median after merging these arrays. ## Method 1:

• Find the union of the given two arrays.
• Sort both array 1 and array2.
• Then the median element will be
Median = (arr1[n-1]+arr2)/2
Run
```#include <stdio.h>

int getMedian(int ar1[], int ar2[], int n)
{
int j = 0;
int i = n - 1;
while (ar1[i] > ar2[j] && j < n && i > -1)
{
int temp = ar1[i];
ar1[i] = ar2[j];
ar2[j] = temp;
i--;
j++;
}

//sort ar1
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){ if(ar1[i]>ar1[j]){
int temp = ar1[i];
ar1[i] = ar1[j];
ar1[j] = temp;
}
}
}

//sort ar2
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){ if(ar2[i]>ar2[j]){
int temp = ar2[i];
ar2[i] = ar2[j];
ar2[j] = temp;
}
}
}

return (ar1[n - 1] + ar2) / 2;
}

int main()
{

int arr1[]={1, 12, 15, 26, 38}, arr2[]={2, 13, 17, 30, 45};
int n = sizeof(arr1)/sizeof(arr1);

printf("%d",getMedian(arr1, arr2, n));

return 0;
}```

`16`

## Method 2 :

• Create variable count. Keep track of count while comparing elements of two arrays.
• Run a loop that will terminate when count > n.
• If count becomes n(For 2n elements), we have reached the median.
• Take the average of the elements at indexes n-1 and n in the merged array.

### Time and Space Complexities :

• Time-Complexity :O(n)
• Space-Complexity : O(1)
Run
```#include <stdio.h>

int getMedian(int ar1[], int ar2[], int n)
{
int i = 0;
int j = 0;
int count;
int m1 = -1, m2 = -1;

for (count = 0; count <= n; count++){
if (i == n){
m1 = m2;
m2 = ar2;
break;
}
else if (j == n){
m1 = m2;
m2 = ar1;
break;
}
if (ar1[i] <= ar2[j]){
/* Store the prev median */
m1 = m2;
m2 = ar1[i];
i++;
}
else{
/* Store the prev median */
m1 = m2;
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}

int main()
{

int arr1[]={1, 12, 15, 26, 38}, arr2[]={2, 13, 17, 30, 45};
int n = sizeof(arr1)/sizeof(arr1);

printf("%d",getMedian(arr1, arr2, n));

return 0;
}```

`16`

## Method 3  :

• Find the medians of the given two arrays and store them in variable say m1 and m2.
• Now, if m1=m2, then that will be the required output.
• If m1>m2, then we check in the subarrays, arr1[0 – middle element] and in arr2[middle element – last].
• If m2>m1, then we check in the subarrays, arr1[middle element – last] and in arr2[0-middle element ].
• This will be the recursive process and repeat this till size of both the arrays become 2.
• As, when the size will be 2 , we can use the formula :

Median = (max(ar1, ar2) + min(ar1, ar2))/2

### Time and Space Complexities :

• Time-Complexity :O(logn)
• Space-Complexity : O(1)
Run
```#include<stdio.h>

int max(int a, int b){
if(a>b)
return a;
return b;
}

int min(int a, int b){
if(a>b)
return b;
return a;
}

/* 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 getMedian(int ar1[], int ar2[], int n)
{

if (n == 1)
return (ar1 + ar2)/2;
if (n == 2)
return (max(ar1, ar2) + min(ar1, ar2)) / 2;

int m1 = median(ar1, n);
int m2 = median(ar2, n);

if (m1 == m2)
return m1;

if (m1 < m2)
{
if (n % 2 == 0)
return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1);
return getMedian(ar1 + n/2, ar2, n - n/2);
}

if (n % 2 == 0)
return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1);
return getMedian(ar2 + n/2, ar1, n - n/2);
}

int main()
{

int arr1[]={1, 12, 15, 26, 38}, arr2[]={2, 13, 17, 30, 45};
int n = sizeof(arr1)/sizeof(arr1);

printf("%d",getMedian(arr1, arr2, n));

return 0;
}```

`16`