Median of Two Sorted Arrays of the Same Size

Given two sorted arrays a and b, both of length n >= 1, return the median of all 2n values. Because 2n is even, the median is the mean of the two middle values.

Example

Text

a = [1, 3],     b = [2, 4]        Output: 2.5   (merged: 1 2 3 4)
a = [1, 2, 9],  b = [3, 4, 7]     Output: 3.5   (merged: 1 2 3 4 7 9)

The general version with different lengths is LeetCode 4.

Brute force: merge up to the middle

Merge the two arrays as in merge sort, but stop after the two middle positions, n - 1 and n.

Java

public class Main {
    static double median(int[] a, int[] b) {
        int n = a.length;
        int i = 0;
        int j = 0;
        int prev = 0;
        int cur = 0;
        for (int step = 0; step <= n; step++) {
            prev = cur;
            if (j == n || (i < n && a[i] <= b[j])) {
                cur = a[i++];
            } else {
                cur = b[j++];
            }
        }
        return ((double) prev + cur) / 2.0;
    }

    public static void main(String[] args) {
        System.out.println(median(new int[] {1, 3}, new int[] {2, 4}) + " " + median(new int[] {1, 2, 9}, new int[] {3, 4, 7}));
    }
}

Output

2.5 3.5

Time: O(n). Space: O(1).

Optimal: binary search for the partition

Take i elements from the front of a and n - i from the front of b. Together they are the lower half of the merged array exactly when every taken element is at most every element left behind:

Text

a[i - 1] <= b[n - i]     and     b[n - i - 1] <= a[i]

(Each array's own elements are already in order.) Binary search i over 0 to n. If a[i - 1] > b[n - i], too much of a was taken, so move left. If b[n - i - 1] > a[i], too little, so move right. At the right partition, the two middle values are the largest taken element and the smallest remaining one.

For a = [1, 2, 9], b = [3, 4, 7]:

i	taken from a	taken from b	check	result
1	[1]	[3, 4]	b's 4 > a's 2	take more of a
2	[1, 2]	[3]	2 <= 4 and 3 <= 9	found: max(2, 3) = 3, min(9, 4) = 4

Missing neighbours at the ends (i = 0 or i = n) are treated as negative infinity on the left and positive infinity on the right. double values print with a decimal point, so the median 7 prints as 7.0.

Java

public class Main {
    static double median(int[] a, int[] b) {
        int n = a.length;
        int lo = 0;
        int hi = n;
        while (true) {
            int i = lo + (hi - lo) / 2; // take i from a, n - i from b
            int j = n - i;
            long aLeft = i > 0 ? a[i - 1] : Long.MIN_VALUE;
            long aRight = i < n ? a[i] : Long.MAX_VALUE;
            long bLeft = j > 0 ? b[j - 1] : Long.MIN_VALUE;
            long bRight = j < n ? b[j] : Long.MAX_VALUE;
            if (aLeft > bRight) {
                hi = i - 1;
            } else if (bLeft > aRight) {
                lo = i + 1;
            } else {
                long lower = Math.max(aLeft, bLeft);
                long upper = Math.min(aRight, bRight);
                return (lower + upper) / 2.0;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(median(new int[] {1, 3}, new int[] {2, 4}) + " " + median(new int[] {1, 2, 9}, new int[] {3, 4, 7}));
        System.out.println(median(new int[] {1, 2}, new int[] {3, 4}) + " " + median(new int[] {5, 6}, new int[] {1, 2}));
        System.out.println(median(new int[] {7}, new int[] {7}));
    }
}

Output

2.5 3.5
2.5 3.5
7.0

Time: O(log n). Space: O(1).

hi = i - 1 never makes hi negative: aLeft > bRight needs a real a[i - 1], so i >= 1. A valid partition always exists, so the loop always returns. The sentinels are Long.MIN_VALUE and Long.MAX_VALUE, so they stay outside the range of every int element.

Edge cases

All of a is smaller than b: the partition is i = n; the middle values are a[n - 1] and b[0].
Equal values across arrays: the checks use <=, so ties are fine.
Overflow: adding two int values can wrap around. The code widens to long (or double) before adding, so the sum is exact.