一、问题

给定两个大小分别为 m 和 n 的排序数组 nums1 和 nums2，要求你在 O(log(m+n)) 的时间复杂度内找出这两个数组的中位数。

二、思路

时间复杂度O(log(n))代表随着操作数增加，剩余操作数递减，如二分法。

首先要建模，对这个问题有一个具体的表达，建模的方式决定了解决问题的难易程度。在这里我就是因为错误建模走错了方向，需要分类讨论的情况越来越多，问题越来越复杂。

首先看到时间复杂度的要求，表明应该与二分法相关，如何把这个问题与二分挂钩呢。这个问题要找两个数组合并后的中位数，实际上，合并后数组的中位数就是将数组分成两半，中间的数就是中位数。换句话说要将这个数组分成两个大小相等的数组，其中一个数组中的最大元素小于另一个数组的最小元素，如下图所示。图片来自4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

可见，问题的关键在于找到这样一个分割线，使得左侧的最大值小于右侧的最小值。

三、题解

class Solution:

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        # 二分查找

        m = len(nums1)

        n = len(nums2)

        if m > n:

            nums1,nums2 = nums2,nums1

            m,n = len(nums1),len(nums2)

        # 从数组1中取line1个数，从数组2中取line2个数组成left，其余是right

        line1 = 0

        infinty = 2**40

        while line1 <= m:

            line2 = (m+n+1)//2 - line1

            maxleft1 = nums1[line1-1] if line1 > 0 else -infinty

            maxleft2 = nums2[line2-1] if line2 > 0 else -infinty

            maxleft = max(maxleft1,maxleft2)

            minright1 = nums1[line1] if line1 < m else infinty

            minright2 = nums2[line2] if line2 < n else infinty

            minright = min(minright1,minright2)

            if maxleft <= minright:

                return maxleft if (m+n)%2 == 1 else (maxleft+minright)/2

            else:

                line1 += 1