Find the Median of an Array

Title: Find the Median of an Array

In this guide, you will learn how to find the median of an array in Java. The median is the middle value of a dataset once it has been ordered, and it is one of the most useful statistics for describing a distribution that may contain outliers.

We will frame the problem, build a full Java program, trace it on a concrete input, and then look at the parity branch, the overflow trap, and the interview follow-ups that most readers run into on this problem.

Understanding the Problem

Given an array of n integers, the median is the value that sits in the middle after the array is sorted. If n is odd, the median is the single middle element at index n / 2. If n is even, the median is the average of the two middle elements at indices n / 2 - 1 and n / 2.

Because the even case produces a fractional result for inputs like [2, 4], the return type must be double. This also quietly matters for the odd case: returning a double there keeps the method signature consistent so callers do not need to branch on array length.

Approach / Algorithm Steps

1. Reject the input early if the array is null or empty, since a median is undefined when there are no values.
2. Copy the array with clone() so the caller’s array is not mutated by the sort.
3. Sort the copy with Arrays.sort, which runs in O(n log n) time.
4. If the length n is odd, return sorted[n / 2] as a double.
5. If the length n is even, cast the lower middle to long, add the upper middle, and divide by 2.0. The long cast prevents the sum of two large int values from overflowing, and the 2.0 forces floating-point division.

Java Program

import java.util.Arrays;

public class ArrayMedian {
    public static double findMedian(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Array must not be null or empty");
        }
        int[] sorted = numbers.clone();
        Arrays.sort(sorted);
        int n = sorted.length;
        if (n % 2 == 1) {
            return sorted[n / 2];
        }
        return ((long) sorted[n / 2 - 1] + sorted[n / 2]) / 2.0;
    }

    public static void main(String[] args) {
        int[] values = {7, 3, 1, 9, 5};
        double median = findMedian(values);
        System.out.println("Median: " + median);
    }
}

Explanation of the Program

The class ArrayMedian exposes a single static method, findMedian, which accepts an int[] and returns a double. The double return type is required because the even-length case can produce a fractional value, and keeping it uniform avoids forcing callers to branch on array length.

The method first guards against null or empty input by throwing an IllegalArgumentException. Returning a sentinel such as Double.NaN here would be dangerous, since NaN propagates through arithmetic silently and the caller may never notice.

Next, the code clones the input into sorted and runs Arrays.sort on the copy. The clone step is deliberate: callers almost always expect their array to come back unchanged, and a method that silently reorders its argument is a classic source of surprising bugs. The sort itself uses the JDK’s dual-pivot quicksort, which runs in O(n log n) time.

The parity check n % 2 == 1 selects between the two cases. When n is odd, the median is simply sorted[n / 2]; integer division sends n / 2 to the correct middle index (for n = 5 that is index 2). When n is even, the two middle values live at indices n / 2 - 1 and n / 2, and the median is their arithmetic mean.

The expression ((long) sorted[n / 2 - 1] + sorted[n / 2]) / 2.0 hides two important Java details. The (long) cast widens the first operand so the + operation is a long addition, which cannot overflow for any pair of int values. The literal 2.0 then forces the division to be floating-point, so the fractional part is preserved for inputs like [2, 5].

The main method is a driver: it builds a small input, calls findMedian, and prints the result. Running it prints Median: 5.0.

Step-by-Step Trace

Let us trace findMedian on the input [8, 3, 1, 6, 4]. The length is 5, which is odd, so the method should return the middle element of the sorted array.

At the end of the sort step, sorted holds the input in non-decreasing order. Once that invariant is in place, the median is a constant-time lookup: index n / 2 for the odd case, or the average of indices n / 2 - 1 and n / 2 for the even case.

Examples

Example 1: Odd-length array

The sorted array has one unique middle element, which is returned as the median.

int[] nums = {7, 3, 1, 9, 5};
double median = findMedian(nums);
System.out.println(median);
// Sorted: [1, 3, 5, 7, 9]
// Output: 5.0

Example 2: Even-length array

With an even length, the median is the mean of the two middle elements, which can be a non-integer.

int[] nums = {10, 2, 8, 4};
double median = findMedian(nums);
System.out.println(median);
// Sorted: [2, 4, 8, 10]
// Output: 6.0

Example 3: Negative values with a fractional median

Negative inputs work the same way, and the 2.0 divisor keeps the half-step visible in the output.

int[] nums = {-5, -1, -3, -2};
double median = findMedian(nums);
System.out.println(median);
// Sorted: [-5, -3, -2, -1]
// Output: -2.5

Common Mistakes to Avoid

The median problem looks simple, but the parity branch and Java’s numeric rules together produce several reliable traps. These are the mistakes learners actually make on this problem.

• Forgetting to sort first – returning numbers[n / 2] on an unsorted array gives whatever happened to be in the middle index, not the median. Sort a copy before indexing.
• Mutating the caller’s array – calling Arrays.sort(numbers) directly reorders the input the caller passed in, which is almost never what they want. Clone the array first and sort the clone.
• Integer division in the even case – writing (sorted[mid - 1] + sorted[mid]) / 2 drops the fractional part, so [2, 5] gives 3.0 instead of 3.5. Divide by 2.0 to force floating-point division.
• Overflow when averaging two large ints – adding two int values close to Integer.MAX_VALUE wraps to a negative number, so the median comes out hugely wrong. Cast one operand to long before the +.
• Reaching for sorted[n / 2] in the even case – picking only the upper middle gives an answer that is biased upward and does not match the standard definition of the median. Average the two middle elements instead.

Edge Cases to Test

Walk through this checklist before you call the solution done. The first few are the ones an interviewer is most likely to probe.

• Empty array
• Null array reference
• Single-element array
• Two-element array (smallest even case)
• All identical elements
• Already sorted and reverse-sorted inputs
• Array containing duplicates around the median
• Integer.MIN_VALUE and Integer.MAX_VALUE both at the two middle positions

Additional Considerations

The sort-based solution runs in O(n log n) time and uses O(n) extra space, because numbers.clone() allocates a fresh array of the same length. If memory is tight and mutating the input is acceptable, dropping the clone brings the space cost down to O(log n) for the sort’s internal stack, but the method should then be renamed and documented so callers know the array will be reordered.

The Integer.MIN_VALUE / Integer.MAX_VALUE edge case matters because Integer.MAX_VALUE + Integer.MAX_VALUE in int arithmetic wraps to -2, and Integer.MIN_VALUE + Integer.MIN_VALUE wraps to 0. The (long) cast on the first operand is what saves us: the + is then evaluated in long, which has enough headroom for any sum of two int values.

A faster alternative is Quickselect, which finds the k-th smallest element in O(n) average time. For an odd-length array it needs one Quickselect call; for an even-length array it needs two, or one call plus a linear scan to recover the larger of the lower half. In practice, Arrays.sort is so well tuned that Quickselect only pays off for very large arrays or latency-sensitive hot paths.

Interview Follow-up Questions

The base problem is only the opening move. A real interviewer will push with questions like these, each probing a different axis of the solution.

• Can you find the median without sorting the whole array? – use Quickselect to partition around the k-th order statistic, reaching O(n) average time with O(1) extra space in the in-place variant.
• How would you maintain the median of a stream of numbers? – keep a max-heap for the lower half and a min-heap for the upper half, rebalancing after every insert so the roots sit on either side of the median.
• What is the median of two sorted arrays? – binary-search the partition point in the smaller array so that the combined left half holds the correct number of elements, giving O(log(min(m, n))) time.
• How would you compute the median of billions of values that do not fit in memory? – use an approximate quantile algorithm such as t-digest or Greenwald-Khanna, which trade a bounded accuracy loss for sub-linear memory.
• How would you compute a weighted median instead of the plain median? – sort the pairs by value, scan while accumulating weights, and return the value at which the cumulative weight first reaches half of the total weight.

Conclusion

Finding the median of an array in Java comes down to three decisions: sort a copy rather than the original, branch on parity to pick either one middle element or the mean of two, and widen to long plus divide by 2.0 so the even case is both overflow-safe and fractional-aware. Once those three habits are in place, the solution extends naturally to streams, to two sorted arrays, and to the approximate variants used at scale.

Try adapting the code above to a Quickselect-based implementation and benchmark it against the sort-based version on a few million random values. The crossover point is often further out than beginners expect.

You can learn more Array problems like this one here: Arrays.