Median of two sorted arrays Program C++

What is Median?

In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.

How to Find median in Arrays:

For getting the median of input array

let int Arr = { 12, 10, 18, 4, 30 }; first sort the array.

We get { 4, 10, 12, 18, 30 } after sorting.

Median is the middle element of the sorted array i.e. 12.

C++ Program to find median of two sorted arrays

#include <iostream>
#include <algorithm>
using namespace std;


int median(int [], int);

/*
 * returns median of ar1[] and ar2[].
 */
int getMedian(int ar1[], int ar2[], int n)
{
    int m1;
    int m2;
    if (n <= 0)
        return -1;
    if (n == 1)
        return (ar1[0] + ar2[0]) / 2;
    if (n == 2)
        return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
    m1 = median(ar1, n);
    m2 = median(ar2, n);
    if (m1 == m2)
        return m1;
    if (m1 < m2)
    {
        if (n % 2 == 0)
            return getMedian(ar1 + n / 2 - 1, ar2, n - n / 2 + 1);
        else
            return getMedian(ar1 + n / 2, ar2, n - n / 2);
    }
    else
    {
        if (n % 2 == 0)
            return getMedian(ar2 + n / 2 - 1, ar1, n - n / 2 + 1);
        else
            return getMedian(ar2 + n / 2, ar1, n - n / 2);
    }
}

/*
 * get median of a sorted array
 */
int median(int arr[], int n)
{
    if (n %  2 == 0)
        return (arr[n / 2] + arr[n / 2 - 1]) / 2;
    else
        return arr[n / 2];
}

/*
 * Main
 */
int main()
{
    int ar1[] = {1, 2, 3, 6};
    int ar2[] = {4, 6, 8, 10};
    int n1 = sizeof(ar1)/sizeof(ar1[0]);
    int n2 = sizeof(ar2)/sizeof(ar2[0]);
    if (n1 == n2)
        cout<<"Median is "<<getMedian(ar1, ar2, n1);
    else
        cout<<"Doesn't work for arrays of unequal size"<<endl;
    return 0;
}

 

OUTPUT:

median of two sorted arrays

Leave a Comment