9. 寻找两个有序数组的中位数

<?php
/**
 * [1, 2, 3, 5]
 * [4, 6, 7, 8, 9]
 * 5
 *
 * @param $nums1
 * @param $nums2
 * @return float|int|mixed
 */
function findMedianSortedArrays($nums1, $nums2) {
    if (count($nums1) > count($nums2)) {
        return findMedianSortedArrays($nums2, $nums1);
    }
    if (count($nums1) == 0) {
        return floor($nums2[count($nums2) - 1] / 2 + $nums2[count($nums2) / 2]) / 2;
    }
    $len = count($nums1) + count($nums2);
    $cut1 = 0;
    $cutL = 0;
    $cutR = count($nums1);
    while ($cut1 <= count($nums1)) {
        // 二分法分割点，$cutL 和 $cutR 分别为上一次左右两边
        // $cut1 >= $cut1
        // $cut2 <= $cut2
        $cut1 = floor(($cutR - $cutL) / 2) + $cutL;
        $cut2 = floor($len / 2) - $cut1;
        // 分割点左边数
        $l1 = ($cut1 == 0) ? PHP_INT_MIN : $nums1[$cut1 - 1];
        $l2 = ($cut2 == 0) ? PHP_INT_MIN : $nums2[$cut2 - 1];
        // 分割点右边数
        $r1 = ($cut1 == count($nums1)) ? PHP_INT_MAX : $nums1[$cut1];
        $r2 = ($cut2 == count($nums2)) ? PHP_INT_MAX : $nums2[$cut2];
        if ($l1 > $r2) {
            $cutR = $cut1 - 1;
        } else if ($l2 > $r1) {
            $cutL = $cut1 + 1;
        } else {
            if ($len % 2 == 0) {
                $l1 = $l1 > $l2 ? $l1 : $l2;
                $r1 = $r1 < $r2 ? $r1 : $r2;
                return ($l1 + $r1) / 2;
            }
            return min($r1, $r2);
        }
    }
}
$nums1 = [1, 2, 3, 5];
$nums2 = [4, 6, 7, 8, 9];
$ret = findMedianSortedArrays($nums1, $nums2);
print_r($ret);