Original problem

https://leetcode.com/problems/median-of-two-sorted-arrays/

Original text

Description

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Example 1

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10⁶ <= nums1[i], nums2[i] <= 10⁶

Solution (PHP 8.2)

Wikipedia

https://en.wikipedia.org/wiki/Median

For a data set x of n elements, ordered from smallest to greatest

$$\text{if}\ n\ \text{is odd,}\ med(x)=x_{(n+1)/2}$$

$$\text{if}\ n\ \text{is even,}\ med(x)=\dfrac{x_{(n/2)}+x_{((n/2)+1)}}{2}$$

function getMedian(array $listX, array $listY): float
{
    $listMerged = \array_merge($listX, $listY);
    \sort($listMerged);

    $listSize = \count($listMerged);
    if (0 === $listSize % 2) {
        $listCenter = $listSize / 2;

        return \bcdiv(
            \bcadd(
                $listMerged[$listCenter - 1],
                $listMerged[$listCenter],
                scale: 5
            ),
            num2: 2,
            scale: 5
        );
    } else {
        $listCenter = ($listSize + 1) / 2;

        return \floatval($listMerged[$listCenter - 1]);
    }
}
Debug
[
-318927389127
-312389712367
-312379128371
3123712987.52234234
4123123541.412342
71982731892
121237681726
12192837128937
]

Tests

List XList YResultTimeMemory
[1,3][2]220μs320B
[1,2][3,4]2.520μs320B
[-312379128371, 4123123541.412342, -312389712367, 121237681726][12192837128937, 3123712987.52234234, -318927389127, 71982731892]3623418264.467320μs320B
[-312379128371, 4123123541.412342, -312389712367, 121237681726][12192837128937, -318927389127, 71982731892]4123123541.41234220μs320B
Verification

$$\dfrac{3123712987.52234234+4123123541.412342}{2}$$

WolframAlpha:

$$3.62341826446734217 × 10^9$$

OS: Ubuntu WSL2 (5.15.146.1-microsoft-standard-WSL2)
CPU: AMD Ryzen 7 5800X
RAM: 16GB

PHP 8.2.17 (cli) (built: Mar 16 2024 08:41:44) (NTS)
Copyright (c) The PHP Group
Zend Engine v4.2.17, Copyright (c) Zend Technologies
    with Zend OPcache v8.2.17, Copyright (c), by Zend Technologies
    with Xdebug v3.3.1, Copyright (c) 2002-2023, by Derick Rethans

memory_limit => -1
xdebug.mode => profile