Given two sorted arrays, merge the two arrays into one single array and find the median of the merged array.
For example:
If the given input is :
5 //size of the array
1 3 5 7 9 //array a
2 4 6 8 10 //array b
Then merged array will be 1 2 3 4 5 6 7 8 9 10
The median will always be middle two element's average as the size of the temp array will be even always.
so, the result is (5+6)/2 = 5 is the median.
Implementation:
For example:
If the given input is :
5 //size of the array
1 3 5 7 9 //array a
2 4 6 8 10 //array b
Then merged array will be 1 2 3 4 5 6 7 8 9 10
The median will always be middle two element's average as the size of the temp array will be even always.
so, the result is (5+6)/2 = 5 is the median.
Implementation:
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int *a,*b,n,i,*temp,j,l,r,mid;
/* Get the number of elements of the array */
scanf("%d",&n);
/* Dynamically allocate the memory block of n integers and store the address of a */
a=(int*)malloc(sizeof(int)*n);
/* Dynamically allocate the memory block of n integers and store the address of b */
b=(int*)malloc(sizeof(int)*n);
/* Dynamically allocate the memory block of 2*n integers and store the address of temp */
temp=(int*)malloc(sizeof(int)*2*n);
/* Get the elements of the array a */
for(i=0;i<n;i++)
scanf("%d",(a+i));
/* Get the elements of the array b */
for(i=0;i<n;i++)
scanf("%d",(b+i));
/* Counter variable for array a */
l=0;
/* Counter variable for array b */
r=0;
/* Counter variable for array temp */
j=0;
/* Until either one of the array becomes empty, store the elements in ascending order in temp */
while(l<n && r<n)
{
if(*(a+l)<*(b+r))
temp[j++]=a[l++];
else
temp[j++]=b[r++];
}
/* If still array b is not empty but array a is empty, copy all the remaining elements of the array b
to temp */
if(l==n)
{
while(r<n)
temp[j++]=b[r++];
}
/* Else if still array a is not empty but array b is empty, copy all the remaining elements of the array a
to temp */
else
{
while(l<n)
temp[j++]=a[l++];
}
/* finally print the temp array to get 2*n merged elements from the two sorted arrays */
for(i=0;i<2*n;i++)
printf("%d ",*(temp+i));
printf("\n");
/* Finding median */
/* After merging n(odd or even) with same n, we always get 2*n as even number */
/* so median is the average of the middle two elements */
mid=(0+(2*n))/2;
/* Printing average of the middle two elements of the merged array temp */
printf("median is %d",(*(temp+mid) + *(temp+mid-1))/2);
/* If you want to write the contents to either a or b array , use the below commented code */
/*
a=(int*)realloc(a,2*n);
for(i=0;i<2*n;i++)
*(a+i)=*(temp+i);
printf("\n");
for(i=0;i<2*n;i++)
printf("%d ",*(a+i));
*/
return 0;
}