Median of Array

Problem Statement

An unsorted array of size n is given. write a program to find the median of an array. The median of array is the middle element of a sorted array in case of odd number of elements in an array and average of middle two elements when the number of elements in an array is even.

Example

Input-1

arr[]: {1, 5, 2, 3, 9, 12, 6}

Output-1

5

Explanation

Here, the sorted sequence of the given array of integers is 1 2 3 5 6 9 12 and the output is 5 because there are odd number of elements in an array that is 7 and and the 4^th^ element in the sorted array will be our answer, which is 5.

Input-2

arr[]: {1, 8, 3, 12, 2, 10, 4, 14}

Output-2

6

Explanation

Here, the sorted array will be 1 2 3 4 8 10 12 14 and the output should be 6 as there is an even number of elements in an array that is 8, So the median will be the average of middle two elements, which is 4 + 8 / 2 = 6.

Constraints

0 <= arr.length <= 1000
-10^6 <= arr[i] <= 10^6

Algorithm 1 – Naive Approach

Intuition:

The brute force approach to find the median of array is to check if the array is sorted or not, the first task is to sort the array, then find the middle element of an sorted array in case of odd number of elements in an array and when the number of elements in an array is even calculate the average of middle two elements (using array indexing).

Algorithm

1. Create a function to find the median of an array that takes the array.
2. First, we will sort the given array.
3. Then check for even case i.e if (size % 2 != 0) return (double)arr[size/2];.
4. In the case of odd numbers of elements in an array return (double)(arr[(size-1)/2] + arr[size/2])/2.0;.

Code Implementation

Code in C++

// Naive Approach to find the median of an array
#include <bits/stdc++.h>
using namespace std;

//calculate median
double median(int arr[], int n){
    // First we will sort the array
   sort(arr, arr+n);
   
   // Check for even case
   if (n % 2 != 0)
      return (double)arr[n/2];
   return (double)(arr[(n-1)/2] + arr[n/2])/2.0;
}
int main(){
   int arr[] = {1, 8, 3, 12, 2, 10, 4, 14};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << median(arr, n) << endl;
   return 0;
}

Code in Java

// Naive Approach to find the median of an array
import java.util.*;

class Main{
    
	// Function for calculating median
	public static double median(int arr[], int n){
		// First we sort the array
		Arrays.sort(arr);

		// even case
		if (n % 2 != 0)
			return (double)arr[n / 2];

		return (double)(arr[(n - 1) / 2] + arr[n / 2]) / 2.0;
	}

	// Driver code
	public static void main(String args[])
	{
		int arr[] = {1, 8, 3, 12, 2, 10, 4, 14};
		int n = arr.length;

		System.out.println(median(arr, n));
	}
}

Code in Python

# Naive Approach to find the median of an array
def median(a, n):

	# First we sort the array
	sorted(a)

	# check for even case
	if n % 2 != 0:
		return float(a[int(n/2)])

	return float((a[(n-1)//2] + a[n//2])/2.0)


# Driver code
a = [1, 8, 3, 12, 2, 10, 4, 14]
n = len(a)

# Function call
print(median(a, n))

Output

6

Time Complexity

The time complexity is O(NlogN). Since we are using Arrays.sort function which requires O(nlogn) time complexity to find the median of unsorted array as it uses merge sort, where n is the size of the given array.

Space Complexity

The space complexity is O(1). Since no extra space is used in the program to find the median of an unsorted array.

Algorithm 2 – Efficient Approach: Using Randomized QuickSelect Algorithm

Intuition:

The previous approach can be optimized in a linear Time O(N) by using the Randomized QuickSelect algorithm. This approach for calculating the median of array is similar to the Quick Sort Algorithm, the difference is the Randomized QuickSelect Algorithm does not actually sort the array.

This algorithm works in two steps. The partitioning step works by picking up the pivot element, then rearranging the elements of the array so that all elements greater than the pivot are on the left side and everything less than the pivot element is on the right side, and the pivot should be in the correct position.

Algorithm

1. Randomly pick up the pivot element from the given array, then rearrange the elements of the array.
2. All elements smaller than the pivot are to the left side and everything less than the pivot element is to the right side, and the pivot should be in the correct position.
3. If the position of the current pivot is the middle of the array then return the pivot as it is the required median of array.
4. If the position of the current pivot is in the left of the middle of an array then repeat all the steps for the subarray starting from the starting index and the pivot as the ending index.
5. If the position of the current pivot is in the right of the middle of an array then repeat all the steps for the subarray starting from the pivot index and ending as the previous ending index.
6. In the odd case i.e if (size % 2 != 0) return arr[size/2];.

Code Implementation

Code in C++

// Efficient Approach to find the median of an array
// using Randomized QuickSelect Algorithm
#include "bits/stdc++.h"
using namespace std;

// swap function
void swap(int* a, int* b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition funciton
int Partition(int arr[], int l, int r){
    int lst = arr[r], i = l, j = l;
    while (j < r) {
        if (arr[j] < lst) {
            swap(&arr[i], &arr[j]);
            i++;
        }
        j++;
    }
    swap(&arr[i], &arr[r]);
    return i;
}
 
// Picks a random pivot element
int randomPartition(int arr[], int l, int r){
    int n = r - l + 1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return Partition(arr, l, r);
}
 
// function
void MedianUtil(int arr[], int l, int r, int k, int& a, int& b){
 
    // if l < r
    if (l <= r) {
 
        // Find the partition index
        int partitionIndex
            = randomPartition(arr, l, r);
 
        // If partition index = k, then
        // we found the median of odd
        // number element in arr[]
        if (partitionIndex == k) {
            b = arr[partitionIndex];
            if (a != -1)
                return;
        }
 
        // If index = k - 1, then we get
        // a & b as middle element of
        // arr[]
        else if (partitionIndex == k - 1) {
            a = arr[partitionIndex];
            if (b != -1)
                return;
        }
 
        // If partitionIndex >= k then
        // find the index in first half
        // of the arr[]
        if (partitionIndex >= k)
            return MedianUtil(arr, l, partitionIndex - 1, k, a, b);
 
        // If partitionIndex <= k then
        // find the index in second half
        // of the arr[]
        else
            return MedianUtil(arr, partitionIndex + 1, r, k, a, b);
    }
 
    return;
}
 
// Function to find Median
void median(int arr[], int n)
{
    int ans, a = -1, b = -1;
 
    if (n % 2 == 1) {
        MedianUtil(arr, 0, n - 1,
                   n / 2, a, b);
        ans = b;
    }

    // Even case
    else {
        MedianUtil(arr, 0, n - 1, n / 2, a, b);
        ans = (a + b) / 2;
    }
    cout << ans;
}
 
// Main code
int main(){
    int arr[] = { 1, 8, 3, 12, 2, 10, 4, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    median(arr, n);
    return 0;
}

Code in Java

// Efficient Approach to find the median of an array
// using Randomized QuickSelect Algorithm
class Main{
	static int a, b;

    // Partition function
	static int Partition(int arr[], int l, int r){
		int lst = arr[r], i = l, j = l;
		while (j < r){
			if (arr[j] < lst){
				arr = swap(arr, i, j);
				i++;
			}
			j++;
		}
		arr = swap(arr, i, r);
		return i;
	}

	// Picks a random pivot
	static int randomPartition(int arr[], int l, int r){
		int n = r - l + 1;
		int pivot = (int) (Math.random() % n);
		arr = swap(arr, l + pivot, r);
		return Partition(arr, l, r);
	}

    static int MedianUtil(int arr[], int l, int r, int k){

        // if l < r
        if (l <= r)
        {

            // Find the partition index
            int partitionIndex = randomPartition(arr, l, r);

            // If partition index = k, then
            // we found the median of odd
            // number element in arr[]
            if (partitionIndex == k)
            {
                b = arr[partitionIndex];
                if (a != -1)
                    return Integer.MIN_VALUE;
            }

            // If index = k - 1, then we get
            // a & b as middle element of
            // arr[]
            else if (partitionIndex == k - 1)
            {
                a = arr[partitionIndex];
                if (b != -1)
                    return Integer.MIN_VALUE;
            }

            // If partitionIndex >= k then
            // find the index in first half
            // of the arr[]
            if (partitionIndex >= k)
                return MedianUtil(arr, l, partitionIndex - 1, k);

            // If partitionIndex <= k then
            // find the index in second half
            // of the arr[]
            else
                return MedianUtil(arr, partitionIndex + 1, r, k);
        }

        return Integer.MIN_VALUE;
    }

	// Function to find Median
	static void median(int arr[], int n){
		int ans;
		a = -1;
		b = -1;

		if (n % 2 == 1){
			MedianUtil(arr, 0, n - 1, n / 2);
			ans = b;
		}

		// Even case
		else{
			MedianUtil(arr, 0, n - 1, n / 2);
			ans = (a + b) / 2;
		}
		System.out.print(ans);
	}
	
	// swap Function
	static int[] swap(int[] arr, int i, int j){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		return arr;
	}

	// Main code
	public static void main(String[] args){
		int arr[] = { 1, 8, 3, 12, 2, 10, 4, 14 };
		int n = arr.length;
		median(arr, n);
	}
}

Code in Python

# Efficient Approach to find the median of an array 
# using Randomized QuickSelect Algorithm
import random

a, b = None, None;

# Partition function
def Partition(arr, l, r) :

	lst = arr[r]; i = l; j = l;
	while (j < r) :
		if (arr[j] < lst) :
			arr[i], arr[j] = arr[j],arr[i];
			i += 1;
		
		j += 1;

	arr[i], arr[r] = arr[r],arr[i];
	return i;

# Picks a random pivot element
def randomPartition(arr, l, r) :
	n = r - l + 1;
	pivot = random.randrange(1, 100) % n;
	arr[l + pivot], arr[r] = arr[r], arr[l + pivot];
	return Partition(arr, l, r);

# Utility function to find median
def MedianUtil(arr, l, r,
				k, a1, b1) :

	global a, b;
	
	# if l < r
	if (l <= r) :
		
		# Find the partition index
		partitionIndex = randomPartition(arr, l, r);
		
		# If partition index = k, then
		# we found the median of odd
		# number element in arr[]
		if (partitionIndex == k) :
			b = arr[partitionIndex];
			if (a1 != -1) :
				return;
				
		# If index = k - 1, then we get
		# a & b as middle element of
		# arr[]
		elif (partitionIndex == k - 1) :
			a = arr[partitionIndex];
			if (b1 != -1) :
				return;
				
		# If partitionIndex >= k then
		# find the index in first half
		# of the arr[]
		if (partitionIndex >= k) :
			return MedianUtil(arr, l,
                              partitionIndex - 1, k, a, b);
			
		# If partitionIndex <= k then
		# find the index in second half
		# of the arr[]
		else :
			return MedianUtil(arr,
                              partitionIndex + 1, r, k, a, b);
			
	return;

# Function to find Median
def findMedian(arr, n) :
	global a;
	global b;
	a = -1;
	b = -1;
	
	if (n % 2 == 1) :
		MedianUtil(arr, 0, n - 1, n // 2, a, b);
		ans = b;
		
	# Even case
	else :
		MedianUtil(arr, 0, n - 1, n // 2, a, b);
		ans = (a + b) // 2;
		
	print(ans);


# Main code
arr = [ 1, 8, 3, 12, 2, 10, 4, 14  ];
n = len(arr);
findMedian(arr, n);

Output

6

Time Complexity

• Best case: O(1)
• Average case : O(N)
• Worst case : O(N^2)

Refer Quick Sort Algorithm complexity analysis for better understanding, where n is the size of the given array.

Space Complexity

The space complexity in the worst case is O(n) , since n recursive calls are made. In the average case, space complexity will be O(logn) in the Program to find median of an unsorted array.

Conclusion

• We have given An unsorted array of size n. we have to write a program to find the median of array. The median of an array is the middle element of a sorted array.
• When the number of elements in an array is even, return the average of the middle two elements i.e arr[size/2];.
• For eg, an array {1, 8, 3, 12, 2, 10, 4, 14} is given, here the output should be 6 because there is an even number of elements in an array that is 8, So the median will be the average of middle two elements, which is (4 + 8) / 2 = 6.
• The naive approach can be optimized in a linear Time O(N) by using Randomized QuickSelect algorithm which is similar to the Quick Sort Algorithm.
• The naive approach takes O(nlogn) time complexity as we are using Arrays.sort function, and O(1) space complexity because no extra space is used.
• On the other hand, the efficient approach to Find the median of unsorted array takes O(n) time complexity and O(logn) as a space complexity because of the call stack.

FAQ

Q. What is the difference between the mean and the median of an array?

A. The Mean of an array is the ratio of the sum of all elements by the total number of elements. whereas the median of an array is the middle element of a sorted array.

Q. How to find the mean of an array?

A. The Mean of an array can be calculated by the sum of all elements divided by the total number of elements i.e sum/n.

Q. How to find the median of an array when the number of elements in an array is even?

A. When the number of elements in an array is even, return the average of the middle two elements i.e arr[size/2];.