# 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 (Using inbuilt sort() function).
• Then the median element will be
Median = (arr1[n-1]+arr2)/2

### Time and Space Complexities :

• Time-Complexity :O(nlogn)
• Space-Complexity : O(1) ## Code for Median of two Sorted arrays of equal size in C++

Run
```#include<bits/stdc++.h>
using namespace std;

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

sort(ar1, ar1 + n);
sort(ar2, ar2 + n);

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

int main()
{
int n;
cin>>n;

int arr1[n], arr2[n];
for(int i=0; i<n; i++)
cin>>arr1[i];

for(int i=0; i<n; i++)
cin>>arr2[i];

cout<<getMedian(arr1, arr2, n);

return 0;
}```
`Input :51 12 15 26 382 13 17 30 45Output :16`

## Method 2 :

• Take the size of the array from the user and store them in the variables say n.
• Create two arrays of size n and then take elements of the respective arrays from the user.
• Now, 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)

## Code for Median of two Sorted arrays of equal size in C++

Run
```#include <bits/stdc++.h>
using namespace std;

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;
}

// Driver Code
int main()
{
int n;
cin>>n;

int arr1[n], arr2[n];

for(int i=0; i<n; i++)
cin>>arr1[i];

for(int i=0; i<n; i++)
cin>>arr2[i];

getMedian(arr1, arr2, n);

return 0;
}

```
`Input :51 12 15 26 382 13 17 30 45Output :16`

## Method 3 (By comparing the median of the two arrays-Divide and Conquer) :

• 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)

## Code for Median of two Sorted arrays of equal size in C++

Run
```#include<bits/stdc++.h>
using namespace std;
/* 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 n;
cin>>n;

int arr1[n], arr2[n];
for(int i=0; i<n; i++)
cin>>arr1[i];

for(int i=0; i<n; i++)
cin>>arr2[i];

cout<<getMedian(arr1, arr2, n);

return 0;
}```
`Input :51 12 15 26 382 13 17 30 45Output :16`