LeetCode 4: Median of Two Sorted Arrays in Java

The direct approach merges both sorted arrays and selects the middle value. It is simple and runs in O(m+n) time.

The optimal method binary-searches the shorter array and partitions both arrays so that the left half contains exactly half of the combined elements.

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        if (a.length > b.length) return findMedianSortedArrays(b, a);

        int m = a.length;
        int n = b.length;
        int low = 0;
        int high = m;

        while (low <= high) {
            int i = (low + high) >>> 1;
            int j = (m + n + 1) / 2 - i;

            int aLeft = i == 0 ? Integer.MIN_VALUE : a[i - 1];
            int aRight = i == m ? Integer.MAX_VALUE : a[i];
            int bLeft = j == 0 ? Integer.MIN_VALUE : b[j - 1];
            int bRight = j == n ? Integer.MAX_VALUE : b[j];

            if (aLeft <= bRight && bLeft <= aRight) {
                if (((m + n) & 1) == 1) {
                    return Math.max(aLeft, bLeft);
                }
                return ((double) Math.max(aLeft, bLeft)
                    + Math.min(aRight, bRight)) / 2.0;
            }

            if (aLeft > bRight) high = i - 1;
            else low = i + 1;
        }

        throw new IllegalArgumentException("Input arrays must be sorted");
    }
}

Time complexity is O(log(min(m,n))) and extra space is O(1). Casting before addition avoids integer overflow when calculating an even-length median.