C++ Program to Find the Median of Two Sorted Arrays using Divide and Conquer

This C++ program shows the method of computing the median of two sorted arrays of equal length. A median is the mid value which separates all lower values from higher values of the merged array resulted from combining two sorted arrays.

Here is the source code of the C++ program to display the median taking two sorted arrays as input. This C++ program is successfully compiled and run on DevCpp,a C++ compiler.The program output is given below.

  1. /*
  2.  * C++ Program to Find the median of two Sorted arrays using Binary Search approach, specifically divide and conquer method.
  3.  */
  4.  
  5. #include<iostream>
  6. #include<stdio.h>
  7. #include<conio.h>
  8. using namespace std;
  9. int min(int a, int b)
  10. {
  11.     int x;
  12.     if (a < b)
  13.     {
  14.         return a;
  15.     }
  16.     else
  17.     {
  18.         return b;
  19.     }
  20. }
  21. int max(int a, int b)
  22. {
  23.     int x;
  24.     if (a > b)
  25.     {
  26.         return a;
  27.     }
  28.     else
  29.     {
  30.         return b;
  31.     }
  32. }
  33. int getMedian(int *ar1, int *ar2, int n)
  34. {
  35.     int x, i, j;
  36.     if (n == 1)
  37.     {
  38.         x = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2;
  39.         cout<<"\n"<<x;
  40.     }
  41.     else
  42.     {
  43.         i = n / 2;
  44.         int *temp1 = new int[i + 1];
  45.         int *temp2 = new int[i + 1];
  46.         if (ar1[i] < ar2[i])
  47.         {
  48.             for (j = 0; j <= i; j++)
  49.             {
  50.                 temp1[j] = ar1[i + j];
  51.                 temp2[j] = ar2[j];
  52.             }
  53.         }
  54.         else if (ar1[i] > ar2[i])
  55.         {
  56.             for (j = 0; j <= i; j++)
  57.             {
  58.                 temp1[j] = ar1[j];
  59.                 temp2[j] = ar2[i + j];
  60.             }
  61.         }
  62.         getMedian(temp1, temp2, i);
  63.     }
  64. }
  65. int main()
  66. {
  67.     int i, x, j;
  68.     cout<<"enter the no of elements to be entered\n";
  69.     cin>>i;
  70.     int *ar1 = new int[i];
  71.     int *ar2 = new int[i];
  72.     cout<<"enter elements of array 1"<<endl;
  73.     for (j = 0; j < i; j++)
  74.     {
  75.         cin>>ar1[j];
  76.     }
  77.     cout<<"enter elements of array 2"<<endl;
  78.     for (j = 0; j < i; j++)
  79.     {
  80.         cin>>ar2[j];
  81.     }  
  82.     getMedian(ar1, ar2, i);
  83.     getch();
  84. }

Output
 
enter the no of elements to be entered
5
enter elements of array 1
1
2
15
26
38
enter elements of array 2
2
13
17
30
45
 
16

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.