Finding the median efficiently in ArrayList in Java

Finding the median efficiently depends on whether the array is sorted or not. Let’s go step by step. ✅

1️⃣ If the Array is Already Sorted

Median is the middle element (or average of two middle elements if even length).

Time complexity: O(1) access.

int[] arr = {1, 3, 5, 7, 9}; // sorted
int n = arr.length;
double median = (n % 2 != 0) ? arr[n/2] : (arr[n/2 - 1] + arr[n/2]) / 2.0;
System.out.println(median); // 5

✅ Fastest if array is sorted.

2️⃣ If the Array is Unsorted

Naive method: Sort the array → pick middle element.

Arrays.sort(arr); // O(n log n)
double median = (n % 2 != 0) ? arr[n/2] : (arr[n/2 - 1] + arr[n/2]) / 2.0;

Time complexity: O(n log n)

3️⃣ Optimal Method: QuickSelect (O(n) average)

Uses partitioning like QuickSort.

Can find k-th smallest element in O(n) average time.

Median is the n/2-th element (0-based index) for odd length.

Example: Median using QuickSelect

import java.util.*;

public class MedianQuickSelect {

    public static int quickSelect(int[] arr, int left, int right, int k) {
        if (left == right) return arr[left];

        int pivotIndex = partition(arr, left, right);
        if (k == pivotIndex) return arr[k];
        else if (k < pivotIndex) return quickSelect(arr, left, pivotIndex - 1, k);
        else return quickSelect(arr, pivotIndex + 1, right, k);
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
                i++;
            }
        }
        int temp = arr[i]; arr[i] = arr[right]; arr[right] = temp;
        return i;
    }

    public static double findMedian(int[] arr) {
        int n = arr.length;
        if (n % 2 != 0) return quickSelect(arr, 0, n - 1, n / 2);
        else {
            int a = quickSelect(arr, 0, n - 1, n / 2 - 1);
            int b = quickSelect(arr, 0, n - 1, n / 2);
            return (a + b) / 2.0;
        }
    }

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

Time complexity: O(n) average, O(n²) worst case (rare)

Space complexity: O(1) (in-place)

4️⃣ Using Heaps (for streaming data)

Maintain two heaps: max-heap for left half, min-heap for right half.

Median = top of heaps.

Useful if array is very large or data comes dynamically.

Time complexity: O(log n) per insertion, O(1) median retrieval

Summary

Method Time Complexity Notes

• Array sorted O(1) Fastest if sorted
• Sort array O(n log n) Simple, works for small arrays
• QuickSelect O(n) average Efficient for unsorted arrays
• Two Heaps O(n log n) total Good for streaming/online median