Program to find the median of two sorted arrays | faceprep

Program to find the median of two sorted arrays of same size and different size are discussed here. Firstly, let us see what is median of the array? 

Median is an element which divides the array into two parts – left and right. So the number of elements on the left side of the array will be equal or less than the number of elements on the right side. Now, let us consider the case of an array with odd number of elements.

Array = [9,11,16,7,2].
Sorted array = [2,7,9,11,16]

In this case, the median of this array is 9, since it divides the array into two parts: [2,7] and [11,16].

Further, let us consider the case of an array with even elements.

Array = [1,2,3,4,5,6]

In such a case, we will take the average between the last element of the left part and the first element of the right part. In this case, the median equals = (3 + 4) / 2 = 3. 5

Median of two sorted arrays of same size

Let us assume that there are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n).

Test cases

Input:
5
1 12 15 26 38
2 13 17 30 45

Output:
16

Explanation: After merging two arrays, we get {1, 2, 12, 13, 15, 17, 26, 30, 38, 45}
Middle two elements are 15 and 17
Average of middle two elements is (15+17)/2 = 16.

// C program to find median of two sorted arrays

#include

int Calculate_median(int a1[], int a2[], int n)
{
int i = 0;
int j = 0;
int cnt;
int x = -1, y = -1;

for (cnt = 0; cnt <= n; cnt++)
{
if (i == n)
{
x = y;
y = a2[0];
break;
}
else if (j == n)
{
x = y;
y = a1[0];
break;
}

if (a1[i] < a2[j])
{
/* Store the prev median */
x = y;
y = a1[i];
i++;
}
else
{
/* Store the prev median */
x = y;
y = a2[j];
j++;}
}
}
int main()
{
int n, i;
printf(“Enter the size: “);
scanf(“%d”,&n);
int a1[n], a2[n];
printf(“\n Enter the first Array elements: \n”);
for(i=0; i<n; i++)
scanf(“%d”,&a1[i]);
printf(“\n Enter the Second Array elements: \n”);
for(i=0; i<n; i++)
scanf(“%d”,&a2[i]);

printf(“Median: %d”, Calculate_median(a1, a2, n));
return 0;
}

// C++ program to find median of two sorted arrays

#include <bits/stdc++.h>
using namespace std;
int Calculate_median(int a1[], int a2[], int n)
{
int i = 0;
int j = 0;
int cnt;
int x = -1, y = -1;

for (cnt = 0; cnt <= n; cnt++)
{
if (i == n)
{
x = y;
y = a2[0];
break;
}
else if (j == n)
{
x = y;
y = a1[0];
break;
}

if (a1[i] < a2[j])
{
/* Store the prev median */
x = y;
y = a1[i];
i++;
}
else
{
/* Store the prev median */
x = y;
y = a2[j];
j++;
}
}

return (x + y)/2;
}
int main()
{
int a1[10], a2[10], n, i;
cin>>n;

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

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

cout << Calculate_median(a1, a2, n) ;
return 0;
}

// Java program to find median of two sorted arrays

import java.util.*;
public class Main
{
static int Calculate_median(int a1[], int a2[], int n)
{
int i = 0;
int j = 0;
int cnt;
int x = -1, y = -1;

for (cnt = 0; cnt <= n; cnt++)
{
if (i == n)
{
x = y;
y = a2[0];
break;
}
else if (j == n)
{
x = y;
y = a1[0];
break;
}

if (a1[i] < a2[j])
{
/* Store the prev median */
x = y;
y = a1[i];
i++;
}
else
{
/* Store the prev median */
x = y;
y = a2[j];
j++;
}
}

return (x + y)/2;
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int num, i;
System.out.println(“Enter the number of elements: “);
num = sc.nextInt();
int a1[] = new int[num];
int a2[] = new int[num];
System.out.println(“Enter the first array elements: “);
for(i=0; i<num; i++)
a1[i] = sc.nextInt();
System.out.println(“Enter the second array elements: “);
for(i=0; i<num; i++)
a2[i] = sc.nextInt();
System.out.println(“Median: “);
System.out.print(Calculate_median(a1, a2, num));
}
}

# Python program to find median of two sorted arrays

def calculate_median (l1, l2, n):
   i=0
   j=0
   x= -1
   y= -1
   for cnt in range(n+1):
       if i == n:
           x = y
           y = l2[0]
           break
       elif j == n:
           x = y
           y = l1[0]
           break
       if l1[i] < l2[j]:
           x = y
           y = l1[i]
           i = i+1
       else:
           x = y
           y = l2[j]
           j = j+1
   return (x + y)/2

num = int(input(“Enter the number of elements: “))
l1 = []
l2 = []
print(“Enter the first array elements: “)
for i in range (num):
   l1.append(int(input()))

print(“Enter the second array elements: “)
for i in range (num):
   l2.append(int(input()))
print(“Median: %d” %calculate_median(l1,l2, num))

Output:

median of two sorted arrays

Median of two sorted arrays of different size

// C program to find median of two sorted arrays

#include

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

if((m + n) % 2 == 1) {
for (count = 0; count <= (n + m)/2; count++) {
if(i != n && j != m){
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n){
m1 = ar1[i++];
}
else{
m1 = ar1[j++];
}
}
return m1;
}

else {
for (count = 0; count <= (n + m)/2; count++) {
m2 = m1;
if(i != n && j != m){
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n){
m1 = ar1[i++];
}
else{
m1 = ar1[j++];
}
}
return (m1 + m2)/2;
}
}

int main()
{
int m,n,i;
printf(“\nEnter the size of array 1 : “);
scanf(“%d”,&m);
printf(“\nEnter the size of array 2 : “);
scanf(“%d”,&n);
int ar1[m];
int ar2[n];

printf(“\nInput the array 1 elements : “);
for(i = 0; i < m; i++)
scanf(“%d”,&ar1[i]);

printf(“\nInput the array 2 elements : “);
for(i = 0; i < n; i++)
scanf(“%d”,&ar2[i]);

printf(“\nMedian of two arrays : “);
printf(“%d”, Median(ar1, ar2, m, n));
printf(“\n”);
getchar();
return 0;
}

// C++ program to find median of two sorted arrays

#include
using namespace std;

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

if((m + n) % 2 == 1) {
for (count = 0; count <= (n + m)/2; count++) {
if(i != n && j != m){
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n){
m1 = ar1[i++];
}
else{
m1 = ar1[j++];
}
}
return m1;
}

else {
for (count = 0; count <= (n + m)/2; count++) {
m2 = m1;
if(i != n && j != m){
m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
}
else if(i < n){
m1 = ar1[i++];
}
else{
m1 = ar1[j++];
}
}
return (m1 + m2)/2;
}
}

int main()
{
int m,n,i;
cout << “\nEnter the size of array 1 : “;
cin >> m;
cout << “\nEnter the size of array 2 : “;
cin >> n;
int ar1[m];
int ar2[n];

cout << “\nInput the array 1 elements : “;
for(i = 0; i < m; i++)
cin >> ar1[i];

cout << “\nInput the array 2 elements : “;
for(i = 0; i < n; i++)
cin >> ar2[i];

cout << “\nMedian of two arrays : “;
cout << Median(ar1, ar2, m, n);
cout << endl;
return 0;
}