01 Jan 2024•Hard•Erlang / PHP

Median of Two Sorted Arrays

Find the median of two sorted arrays in logarithmic time.

Problem

Given two sorted arrays of sizes m and n, return the median of the two arrays combined. The required run time is O(log(m + n)).

Approach

Merging the arrays would take linear time, so instead binary search for a partition. Split both arrays so that the left halves together hold half of all the elements.

Binary search over the cut position in the shorter array; the cut in the longer array follows from it. A partition is correct when the largest value on the left side of each array is no bigger than the smallest value on the right side of the other array.

Once the partition is correct, the median is the largest left value for an odd total, or the average of the largest left value and the smallest right value for an even total. Treat a cut at either end of an array as negative or positive infinity.

The solution files below implement this approach.

Complexity

Time: O(log(min(m, n))): the binary search runs over the shorter array.
Space: O(1).

Edge cases

One array can be empty; the median then comes from the other array alone.
Arrays of very different lengths are why the search runs over the shorter one.
Even and odd combined lengths need different final steps.

Solution files

PHP•median-of-two-sorted-arrays/solution-v1.php

class Solution {

function findMedianSortedArrays($nums1, $nums2) {
    if (count($nums1) > count($nums2)) {
        return $this->findMedianSortedArrays($nums2, $nums1);
    }

    $m = count($nums1);
    $n = count($nums2);
    $imin = 0;
    $imax = $m;
    $half_len = intval(($m + $n + 1) / 2);

    while ($imin <= $imax) {
        $i = intval(($imin + $imax) / 2);
        $j = $half_len - $i;
        if ($i < $m && $nums1[$i] < $nums2[$j - 1]) {
            $imin = $i + 1;
        } elseif ($i > 0 && $nums1[$i - 1] > $nums2[$j]) {
            $imax = $i - 1;
        } else {
            $max_of_left = 0;
            if ($i == 0) { 
                $max_of_left = $nums2[$j - 1];
            } elseif ($j == 0) { 
                $max_of_left = $nums1[$i - 1];
            } else { 
                $max_of_left = max($nums1[$i - 1], $nums2[$j - 1]);
            }

            if (($m + $n) % 2 == 1) {
                return $max_of_left;
            }

            $min_of_right = 0;
            if ($i == $m) {
                $min_of_right = $nums2[$j];
            } elseif ($j == $n) {
                $min_of_right = $nums1[$i];
            } else {
                $min_of_right = min($nums1[$i], $nums2[$j]);
            }

            return ($max_of_left + $min_of_right) / 2.0;
        }
    }

    return 0.0;
}
}

Erlang•median-of-two-sorted-arrays/solution.erl

Solution file content could not be loaded.

PHP•median-of-two-sorted-arrays/solution.php

class Solution {

function findMedianSortedArrays($nums1, $nums2) {
    $m = count($nums1);
    $n = count($nums2);

    if ($m > $n) {
        list($nums1, $nums2) = array($nums2, $nums1);
        list($m, $n) = array($n, $m);
    }
    
    $m = count($nums1);
    $nnn = count($nums2);
    $immin = 0;
    $imax = $m;
    $half_len = intval(($m + $n + 1) / 2);

    while ($imin <= $imax) {
        $i = intval(($imin + $imax) / 2);
        $j = $half_len - $i;
        if ($i < $m && $nums1[$i] < $nums2[$j - 1]) {
            $imin = $i + 1;
        } elseif ($i > 0 && $nums1[$i - 1] > $nums2[$j]) {
            $imax = $i - 1;
        } else {
            $max_of_left = 0;
            if ($i == 0) {
                $max_of_left = $nums2[$j -1];
            } elseif ($j == 0) {
                $max_of_left = $nums1[$i - 1];
            } else {
                $max_of_left = max($nums1[$i - 1], $nums2[$j - 1]);
            }

            if (($m + $n) % 2 == 1) {
                return $max_of_left;
            }

            $min_of_right = 0;
            if ($i == $m) {
                $min_of_right = $nums2[$j];
            } elseif ($j == $n) {
                $min_of_right = $nums1[$i];
            } else {
                $min_of_right = min($nums1[$i], $nums2[$j]);
            }

            return ($max_of_left + $min_of_right) / 2.0;
        }

    }
    return 0.0;
}
}