Arrays: Find the median of 2 sorted arrays of same size

Problem Statement:

You are given 2 sorted arrays of same size. You need to obtain the median (middle) of the array.

But first, what is a median?

Median is an element separating higher half of the data from a lower half. It can be thought of as a middle value.

Let n be the size of an array then,

If n is odd then median = value of ((n+1)/2)th element
If n is even then median = value of [(n/2)th element + (n/2+1)element]/2

Example:

A = 2, 6, 9
B = 1, 5, 7
Combined array: 1, 2, 5, 6, 7, 9
As the array is even, we take element at index 3 and index 4
So the median will be = (5+6)/2 = 5.5

Solution:

We can solve it by many approaches, some of them discussed are:

1. Simple Approach

In this approach, we will have to find the 2 elements that could be in the middle when the 2 arrays are merged in sorted order.

For this, we follow the merge procedure like in merge sort.
Then we compare the values at the two pointers pointing at two index of the 2 arrays and then incrementing accordingly.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_set>

using namespace std;

int get_median_by_comparing(int ar1[], int ar2[], int n)
{
    int i = 0; 
    int j = 0; 
    int count;
    int m1 = -1, m2 = -1;
 
    for (count = 0; count <= n; count++)
    {

        if (i == n)
        {
            m1 = m2;
            m2 = ar2[0];
            break;
        }

        else if (j == n)
        {
            m1 = m2;
            m2 = ar1[0];
            break;
        }

        if (ar1[i] <= ar2[j])
        {
            m1 = m2; 
            m2 = ar1[i];
            i++;
        }
        else
        {
            m1 = m2; 
            m2 = ar2[j];
            j++;
        }
    }
 
    return (m1 + m2)/2;
}

int main()
{
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45};
    int n1 = sizeof(ar1)/sizeof(ar1[0]);

     cout<<"The median by using comparing method is = "<< get_median_by_comparing(ar1, ar2, n1)<<endl;

    return 0;
}

Output:

The median by using comparing method is = 16