寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

• nums1.length == m

• nums2.length == n

• 0 <= m <= 1000

• 0 <= n <= 1000

• 1 <= m + n <= 2000

• -106 <= nums1[i], nums2[i] <= 106

完成以上要求，再看下面参考答案

=========================================================================

=========================================================================

class Solution:
    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
        # 确保nums1是较短的数组，减少二分次数
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        
        m, n = len(nums1), len(nums2)
        total_left = (m + n + 1) // 2  # 左半部分的总长度（奇数时左半多一个）
        
        # 二分查找的边界：nums1的左半部分可以取0~m个元素
        left, right = 0, m
        
        while left < right:
            # i: nums1左半部分的元素个数，j: nums2左半部分的元素个数
            i = left + (right - left + 1) // 2  # 取上中位数，避免死循环
            j = total_left - i
            
            # 调整二分边界：nums1左半最后一个 > nums2右半第一个 → 减少nums1左半
            if nums1[i-1] > nums2[j]:
                right = i - 1
            else:
                left = i  # 否则扩大nums1左半
        
        # 最终确定的分割点
        i = left
        j = total_left - i
        
        # 处理边界情况（某侧没有元素）
        nums1_left_max = nums1[i-1] if i > 0 else float('-inf')
        nums1_right_min = nums1[i] if i < m else float('inf')
        nums2_left_max = nums2[j-1] if j > 0 else float('-inf')
        nums2_right_min = nums2[j] if j < n else float('inf')
        
        # 计算中位数
        if (m + n) % 2 == 1:
            # 总长度奇数：左半最大值就是中位数
            return max(nums1_left_max, nums2_left_max)
        else:
            # 总长度偶数：左右半最值的平均值
            return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0
​
# 如果你需要在本地测试，可以保留下面的代码（提交到LeetCode时可以删除）
if __name__ == "__main__":
    sol = Solution()
    # 示例1
    nums1 = [1,3]
    nums2 = [2]
    print(sol.findMedianSortedArrays(nums1, nums2))  # 输出 2.0
    
    # 示例2
    nums1 = [1,2]
    nums2 = [3,4]
    print(sol.findMedianSortedArrays(nums1, nums2))  # 输出 2.5