How can I get the median of an unordered list in Java

ben_11 0
Viewed 52

How can I calculate the median of an unorder Java list?

Here is the code I have written so far:

public class MockTest1 {
    /*
     given a random list of integers, find the median e.g. given the list [1, 4, 2, 3, 5] the median is 3 
    */
    
    public static void main(String[] args) {
        List<Integer> array = List.of(1, 3, 4, 5, 2);
        
        System.out.println(getMedian(array));
    }
    
    public static int getMedian(List<Integer> arr) {
        ArrayList<Integer> list = new ArrayList<>(arr);
        
        Collections.sort(list);
        
        double length = (double) list.size();
        
        int med = (int) Math.ceil(length / 2);
        
        return list.get(med - 1);
    }
}

I converted the list to an arraylist to make it mutable.

For the example I'm using, i.e., [1, 3, 4, 5, 2] I am getting an ouput of 4 instead of 3, my concensus from this is that the list is not remaining sorted when I call the get method, how do I solve this problem?

math java
1 Answers

The list in your example is [1, 2, 3, 4, 5] (sorted), that is value 1 is found at index 0, 2 at index 1, 3 at index 2 and so on. The size of the list is 5. The median can be found at index 5 / 2 == 2 (integer division).

    public static int getMedian(List<Integer> arr) {
        ArrayList<Integer> list = new ArrayList<>(arr);
        
        Collections.sort(list);
        return list.get(list.size() / 2);
    }

Update

Although it was not part of the original question, the median of a list of even size is defined as the average of the two elements which are around the middle of the list. Let's assume [1, 2, 3, 4, 5, 6], then there is no single element in the middle of the list. Instead, the median is the average of the two 'middle' elements 3 and 4, that is (3+4)/2.0. This is a floating point value, so the return type has to change as well as the calculation:

public static double getMedian(List<Integer> arr) {
    if (arr.isEmpty()) {
        throw new IllegalArgumentException("Can't calculate the median of an empty list");
    }

    ArrayList<Integer> list = new ArrayList<>(arr);
    Collections.sort(list);

    int medianIndex = list.size() / 2;
    double median;
    if (list.size() % 2 == 0) {
        double upper = list.get(medianIndex).doubleValue();
        double lower = list.get(medianIndex - 1).doubleValue();
        median = (lower + upper) / 2.0;
    } else {
        median = list.get(medianIndex).doubleValue();
    }
    return median;
}
Mihe0
Related