C++ Programming Code Examples C++ > Sorting Searching Code Examples C++ Program to Find Median of Two Sorted Arrays C++ Program to Find Median of Two Sorted Arrays This is a C++ Program find the median of elements where elements are stored in 2 different arrays. - We need to find combined median of two different data set. - It includes sorting of both arrays using quick sort and then printing the median by simultaneously traversing both arrays. - The time complexity will be O(n*log(n)+m*log(m)+m+n). - Take input of both the data set of length m and n respectively. - Sort the data sets using the quick-sort algorithm. - Calculate the median, considering both arrays as a single array. - Exit. #include<iostream> using namespace std; // Swapping two values. void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } // Partitioning the array on the basis of values at high as pivot value. int Partition(int a[], int low, int high) { int pivot, index, i; index = low; pivot = high; // Getting index of pivot. for(i=low; i < high; i++) { if(a[i] < a[pivot]) { swap(&a[i], &a[index]); index++; } } // Swapping value at high and at the index obtained. swap(&a[pivot], &a[index]); return index; } // Implementing QuickSort algorithm. int QuickSort(int a[], int low, int high) { int pindex; if(low < high) { // Partitioning array using randomized pivot. pindex = Partition(a, low, high); // Recursively implementing QuickSort. QuickSort(a, low, pindex-1); QuickSort(a, pindex+1, high); } return 0; } int main() { int n, m, bi, ai, i, k; double median; cout<<"Enter the number of element in the first data set: "; cin>>n; int a[n]; // Take input of first sequence. for(i = 0; i < n; i++) { cout<<"Enter "<<i+1<<"th element: "; cin>>a[i]; } cout<<"\nEnter the number of element in the second data set: "; cin>>m; int b[m]; // Take input of second sequence. for(i = 0; i < m; i++) { cout<<"Enter "<<i+1<<"th element: "; cin>>b[i]; } // Sort the data of both arrays. QuickSort(a, 0, n-1); QuickSort(b, 0, m-1); //Print the result. cout<<"\tThe Median from these data set is: "; ai = 0; bi = 0; // If the m+n is odd then one median will be there otherwise average of two will be taken as median. if((m+n)%2 == 1) { // K is the number of element present upto the median from the beginning of the data array. k =(n+m)/2+1; while(k > 0) { // Compare current element of array 'a' and 'b' and skip next the smaller one. if(a[ai] <= b[bi] && ai < n) { k--; // Print if we have skipped k element. if(k == 0) cout<<a[ai]; ai++; } else if(a[ai] > b[bi] && bi < m) { k--; // Print if we have skipped k element. if(k == 0) cout<<b[bi]; bi++; } } } else { k = (n+m)/2+1; while(k > 0) { // Compare current element of array 'a' and 'b' and skip next the smaller one. if(a[ai] <= b[bi] && ai < n) { k--; // Add the last two numbers so as we can calculate average. if(k <= 1) median += a[ai]; ai++; } else if(a[ai] > b[bi] && bi < m) { k--; // Add the last two numbers so as we can calculate average. if(k <= 1) median += b[bi]; bi++; } } // Take average. cout<<median/2; } }