Java – Find median of unsorted array

In this article, we will take a look at 2 different ways to find median of elements of an array with programs and their explanation.
Before diving into the solution, it is better to know the meaning of median of array values.
What is Median ?
Median of a sequence(or an array) of numbers is the middle element of the sequence when the total number of elements is odd or the average of middle elements when the total number of elements is even, provided the sequence is sorted.
Example,

When total elements are odd

Consider the sequence: 2, 3, 6, 12, 15, 34, 65, 78, 99
Total number of elements:     9(odd)
Median will be 5th element: 15

When total elements are even

Consider the sequence: 2, 3, 6, 12, 15, 34, 65, 78
Total number of elements:     8(even)
Median will be average of 5th element: (12 + 15)/2 = 13.5

Thus,

If n is odd then Median (M) = value of ((n + 1)/2)th item term.
If n is even then Median (M) = value of [((n)/2)th item term + ((n)/2 + 1)th item term ]/2

where,
n is the total number of elements in the sequence or array.

How to calculate Median in java
Following are the different ways in which you can calculate median in a java program.

Method 1 : Finding the middle element
Program is given below

public class MedianFinder {
   public static void main(String[] args) {
     // initialize array with odd number of element
     int[] values = { 2, 3, 6, 12, 15, 34, 65, 78, 99 };
     // calculate median
     double median = median(values);
     System.out.println("Median is : " + median);
     // re-initialize array with even number of element
     values = { 2, 3, 6, 12, 15, 34, 65, 78};
     // calculate median
     median = median(values);
     System.out.println("Median is : " + median);
  }

  static double median(int[] values) {
     // sort array
     Arrays.sort(values);
     double median;
     // get count of scores
     int totalElements = values.length;
     // check if total number of scores is even
     if (totalElements % 2 == 0) {
        int sumOfMiddleElements = values[totalElements / 2] +
                                  values[totalElements / 2 - 1];
        // calculate average of middle elements
        median = ((double) sumOfMiddleElements) / 2;
     } else {
        // get the middle element
        median = (double) values[values.length / 2];
  }
  return median;
 }
}

Above program initializes arrays with an odd number of elements and even number of elements and passes these arrays to a method which calculates median.
This method firsts sorts the array using sort() method of java.util.Arrays class.

After this, it checks if the total number of elements of array is even or odd by taking modulus of total elements with 2 and comparing the remainder with 0.
If the remainder is 0, the number of elements are even else they are odd.

1. If the total elements are odd
,
it retrieves the middle element by dividing the total number of elements by 2.
2. If the total elements are even,
it calculates the sum of middle two elements(12 and 15) and divides this sum by 2 to calculate the average of middle elements.

Output

Median is : 15
Median is : 13.5

Method 2 : Using Apache Math Library
Apache Math library provides many utility classes and methods to calculate mathematical entities and solution to programming problems such as mean, median, matrix operations, complex numbers, probability distribution and many more.

This library has a class Median in package org.apache.commons.math3.stat.descriptive.rank.
Median has a median method which takes an array and returns the median value from these array elements.

median method takes a double array as argument. Thus if you have an integer array, then you need to convert it to an array of double elements.

Usage of this library to calculate median is shown below

public class MedianFinder {
    public static void main(String[] args) {
      // initialize array
      double[] values = { 1.2, 3, 4, 5, 8 };
      // calculate median
      double median = median(values);
      System.out.println("Median is : " + median);
    }

    static double median(double[] values) {
      // create an object of Median class
      Median median = new Median();
      // calculate median
      double evaluate = median.evaluate(values);
      return median;
    }
}

Output

Median is : 4.0

Note that now no sorting of array is required and you do not need to check the length of the array and provide different handling as per the total elements being odd or even, the library handles this stuff itself.

Apache commons library can be found at this link.

Click the clap below if the post was helpful.

Leave a Reply