Problem: 4. 寻找两个正序数组的中位数

题目

给定两个大小分别为 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

思路

定义numus1为较小数组，nums2为较大数组
假设有一条分界线在两个数组nums1和nums2中
这个分界线满足两个条件：

性质1：

根据这一性质，我们定义分界线左边的元素个数，可以只二分小的那个nums就可以确定分割线的位置

性质2：

根据这一性质，我们可以写出二分搜索的判断条件，即左上>右下或者左下>右上都不符合我们的分界线要求

我们发现数组下标i就是nums1分割线左边的元素个数，那么同理 total_left-i 就是nums2分割线右边的元素的位置

我们同时要考虑边界情况，如果 i=0 或者 i=m 或者 j=0 或者 j = n的情况，我们将他们取一个极大的数或者极小的数，为什么这样取，读者可以看最终返回的答案的规则

关于最后的答案，如果 m+n 是奇数，我们只需要取nums1和nums2的分界线左边最大点即可；如果 m + n 是偶数，我们需要取得分界线左边的最大值和分界线右边的最小值的和的二分之一。

复杂度

时间复杂度:

$O(log(min(m,n))$

空间复杂度:

$O(1)$

Code

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # nums1 是较小的数组，nums2是较大的数组
        if len(nums1) > len(nums2):
            nums1,nums2 = nums2,nums1

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

        total_left = (m+n+1) // 2
        
        # 从小的数组nums1开始二分
        left = 0
        rigth = m

        while left<rigth:
            i = (left+rigth+1) // 2 # nums1的分界线的右边的节点
            j = total_left - i  # nums2的分界线的右边的节点
            if nums1[i-1] > nums2[j]: # nums1分界线左边的点小于nums2分界线右边的点
                rigth = i-1
            else:
                left = i
        
        i = left
        j = total_left - i

        # 处理边界情况
        nums1_left = nums1[i-1] if i>0 else float('-inf')
        nums1_right = nums1[i] if i<m else float('inf') 

        nums2_left = nums2[j-1] if j>0 else float('-inf')
        nums2_right = nums2[j] if j<n else float('inf')

        if (m+n) % 2 == 1: # 如果 m+n 是奇数，我们只需要取nums1和nums2的分界线左边最大点即可
            return max(nums1_left,nums2_left)
        else: # 如果 m + n 是偶数，我们需要取得分界线左边的最大值和分界线右边的最小值的和的二分之一
            return (max(nums1_left,nums2_left)+min(nums1_right,nums2_right)) / 2