Median of Array (Unsorted)

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

Output-1

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

Output-2

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

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++

Code in Java

Code in Python

Output

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++

Code in Java

Code in Python

Output

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.