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