Find Median of the given Array

Problem Statement: Given an unsorted array, find the median of the given array.

Examples:

Example 1:
Input: [2,4,1,3,5]
Output: 3

Example 2:
Input: [2,5,1,7]
Output: 3.5

What is a Median?

Median is defined as the value which is present in the middle for a series of values. Note, in order to find the median of an array of integers, we must make sure they are sorted.

Mathematically,

Intuition : 

The problem requires us to simply implement the mathematical formula programmatically. Hence, we need to make sure that the array is sorted and calculate the answer based on whether n is odd or even.

Approach : 

  • Sort the array in ascending order
  • Check whether n is odd or even
  • Calculate the median accordingly. Here’s a quick demonstration of the same

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
void getMedian(int arr[],int n)
{
    sort(arr,arr+n);
    if(n%2==0)
    {
        int ind1 = (n/2)-1;
        int ind2 = (n/2);
        cout<<(double)(arr[ind1]+arr[ind2])/2;
    }
    else
    {
        cout<<arr[(n/2)];
    }
}
int main()
{
    int arr[] = {4,7,1,2,5,6};
    int n = 6;
    cout<<"The median of the array is: ";
    getMedian(arr,n);
    return 0;
}

Output:

The median of the array is: 4.5

Time Complexity: O(N*log N), Sorting of array

Space Complexity: O(1)

Java Code

import java.io.*;
import java.util.Arrays;
class Test
{
static private void getMedian(int[] arr, int n)
{
	Arrays.sort(arr);
	
	if (n % 2 == 0)
	{
		int ind1 = (n / 2) - 1;
		int ind2 = (n / 2);
		System.out.print((double)(arr[ind1] + arr[ind2]) / 2);
	}
	else
	{
		System.out.print(arr[(n / 2)]);
	}
}
public static void main(String[] args)
{
	int[] arr = {4, 7, 1, 2, 5, 6};
	int n = 6;
	System.out.print("The median of the array is: ");
	getMedian(arr, n);
}
}

Output:

The median of the array is: 4.5

Time Complexity: O(N*log N), Sorting of array

Space Complexity: O(1)

Special thanks to Naman Daga for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article