[4] 寻找两个正序数组的中位数

链接：寻找两个正序数组的中位数

两个递增数组找中位数，最终结果一定是，通过两条线分别划分两个数组，使得两个左半数组的元素个数之和与两个右半数组元素之和相等或者大1（即总数为奇数时，将中位数放到左边）。

只要给定两个数组的长度m和n，左边的元素个数时确定的，左边的元素个数，这里的除法为计算机整除，向下取整。

当m+n为奇数时，比如2+3，，中位数刚好是左边最大的值
当m+n为偶数时，比如2+2，，左边刚好有一半数据，中位数为左边最大和右边最小的平均值。

由于左边元素个数是确定的，当我门在nums1中随便划分，确定nums1中左边元素个数时（），nums2中左边元素的个数也随之确定()，因为是在nums1中划分的，为了避免超出nums2的长度范围，都默认nums1的元素个数小于nums2（即）。

因此我们可以在nums1中不停的移动，来不停划分nums1，并根据计算出来的划分nums2，并检验划分后的左边最大值小于右边最小值是否满足（等价于 <= nums1[i]），如果满足就找到了合适的划分。就可以根据的奇偶性来计算中位数：

1. 为偶数，返回左边最大值和右边最小值的平均值。
2. 为奇数，返回左边最大值。

在nums1中移动，这个过程可以使用二分查找来加速，定义两个下标，每次都取的中点，即（或，根据下标的更新方式选择）。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        
        m = len(nums1)
        n = len(nums2)
        left_size = (m+n+1) // 2
        # print("m:{}, n:{}, left_size:{}".format(m, n, left_size))

        left = 0
        right = m

        # nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]
        while left < right:
            i = (left + right + 1) // 2
            j = left_size - i
            # print("left:{}, right:{}, i:{}, j:{}".format(left, right, i, j))
            if nums1[i-1] > nums2[j]:
                right = i-1
            else:
                # nums2[j-1] > nums1[i]
                left = i

        i = left
        j = left_size - left
        nums1_left_max = nums1[i-1] if i > 0 else -2**40
        nums2_left_max = nums2[j-1] if j > 0 else -2**40
        nums1_right_min = nums1[i] if i < m else 2**40
        nums2_right_min = nums2[j] if j < n else 2**40

        if (m+n) % 2 == 1:
            return float(max(nums1_left_max, nums2_left_max))
        else:
            return (float(max(nums1_left_max, nums2_left_max)) + float(min(nums1_right_min, nums2_right_min)))/2

二分查找中点选取技巧

二分查找一般需要计算两个下标的中点，通常有两个计算方法，

这两种方法选择主要和的更新方式有关，主要是为了避免区间只有两个数时，算法进入死循环。

如果我们的按下面的方法更新，按计算，可能会死循环。比如循环迭代到时，some_contition条件满足，这时候，下标一直停留在，无法移动，算法无法终止，进入死循环。

while left < right:
    if some_condition:
        left = m
    else:
        right = m-1

但是换成就没有问题，这时，下标从移动到，刚好，循环结束。

同理，当按下面的方法更新时，也可能会死循环。

while left < right:
    if some_condition:
        left = m+1
    else:
        right = m

总结一句话：下标设置为中点时，中点靠右取整（分子+1），下标设置为中点时，中点靠左取整（分子不加1）。