Median of Two Sorted Arrays

Binary search where to cut the shorter array. The cut in the longer array follows, and the cut is right when every value on the left is no bigger than every value on the right.

The idea

The median splits all m + n values into a lower half and an upper half. Take i values from the front of nums1 and j = half - i from the front of nums2: that is a valid lower half exactly when the last value taken from each array is no bigger than the first value left in the other (aL <= bR and bL <= aR). If aL > bR, too many came from nums1, so i must shrink; if bL > aR, too few, so i must grow. That is a binary search on i, and doing it over the shorter array keeps j inside nums2.

Code

public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.Length > nums2.Length) return FindMedianSortedArrays(nums2, nums1);
    int m = nums1.Length, n = nums2.Length, half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2; // values taken from nums1 into the left half
        int j = half - i;           // the rest of the left half comes from nums2
        int aL = i == 0 ? int.MinValue : nums1[i - 1];
        int aR = i == m ? int.MaxValue : nums1[i];
        int bL = j == 0 ? int.MinValue : nums2[j - 1];
        int bR = j == n ? int.MaxValue : nums2[j];
        if (aL > bR) hi = i - 1; // took too many from nums1
        else if (bL > aR) lo = i + 1; // took too few from nums1
        else { // every left value <= every right value
            if ((m + n) % 2 == 1) return Math.Max(aL, bL);
            return (Math.Max(aL, bL) + (long)Math.Min(aR, bR)) / 2.0;
        }
    }
    throw new ArgumentException("Inputs must be sorted.");
}

Tips

• Search the shorter array: with m <= n, j = half - i always lands between 0 and n, so no index goes out of range.
• Missing neighbours act as -∞ and +∞ (the dashed boxes): a cut at the very start or end of an array then passes its check by itself.
• half = (m + n + 1) / 2 puts the extra value of an odd total on the left, so an odd median is simply max(aL, bL).

In the .NET library

int.MinValue and int.MaxValue stand in for the missing neighbours. Cast one side to long before adding the two middle values so two large ints cannot overflow before the division by 2.0.