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.

```
/*
```

 * C++ Program to Find the median of two Sorted arrays using Binary Search approach, specifically divide and conquer method.

```
 */
```
```
 
```
```
#include<iostream>
```
```
#include<stdio.h>
```
```
#include<conio.h>
```
```
using namespace std;
```
```
int min(int a, int b)
```
```
{
```
```
    int x;
```
```
    if (a < b)
```
```
    {
```
```
        return a;
```
```
    }
```
```
    else
```
```
    {
```
```
        return b;
```
```
    }
```
```
}
```
```
int max(int a, int b)
```
```
{
```
```
    int x;
```
```
    if (a > b)
```
```
    {
```
```
        return a;
```
```
    }
```
```
    else
```
```
    {
```
```
        return b;
```
```
    }
```
```
}
```

int getMedian(int *ar1, int *ar2, int n)

```
{
```
```
    int x, i, j;
```
```
    if (n == 1)
```
```
    {
```

        x = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2;

```
        cout<<"\n"<<x;
```
```
    }
```
```
    else
```
```
    {
```
```
        i = n / 2;
```
```
        int *temp1 = new int[i + 1];
```
```
        int *temp2 = new int[i + 1];
```
```
        if (ar1[i] < ar2[i])
```
```
        {
```
```
            for (j = 0; j <= i; j++)
```
```
            {
```
```
                temp1[j] = ar1[i + j];
```
```
                temp2[j] = ar2[j];
```
```
            }
```
```
        }
```
```
        else if (ar1[i] > ar2[i])
```
```
        {
```
```
            for (j = 0; j <= i; j++)
```
```
            {
```
```
                temp1[j] = ar1[j];
```
```
                temp2[j] = ar2[i + j];
```
```
            }
```
```
        }
```
```
        getMedian(temp1, temp2, i);
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int i, x, j;
```

    cout<<"enter the no of elements to be entered\n";

```
    cin>>i;
```
```
    int *ar1 = new int[i];
```
```
    int *ar2 = new int[i];
```

    cout<<"enter elements of array 1"<<endl;

```
    for (j = 0; j < i; j++)
```
```
    {
```
```
        cin>>ar1[j];
```
```
    }
```

    cout<<"enter elements of array 2"<<endl;

```
    for (j = 0; j < i; j++)
```
```
    {
```
```
        cin>>ar2[j];
```
```
    }  
```
```
    getMedian(ar1, ar2, i);
```
```
    getch();
```
```
}
```

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.

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

« Prev - C++ Program to Encrypt Message using Playfair Cipher

» Next - N Queen Problem in C++

Related Posts:

Recommended Articles: