鏈接：尋找兩個正序數(shù)組的中位數(shù)

兩個遞增數(shù)組找中位數(shù)，最終結(jié)果一定是础钠，通過兩條線分別劃分兩個數(shù)組抒抬，使得兩個左半數(shù)組的元素個數(shù)之和與兩個右半數(shù)組元素之和相等或者大1（即總數(shù)為奇數(shù)時，將中位數(shù)放到左邊）炬藤。

只要給定兩個數(shù)組的長度m和n，左邊的元素個數(shù)時確定的豪嚎，左邊的元素個數(shù)细卧，這里的除法為計算機整除，向下取整郊闯。

當m+n為奇數(shù)時妻献，比如2+3，团赁，中位數(shù)剛好是左邊最大的值
當m+n為偶數(shù)時育拨，比如2+2，欢摄，左邊剛好有一半數(shù)據(jù)熬丧，中位數(shù)為左邊最大和右邊最小的平均值。

由于左邊元素個數(shù)是確定的剧浸，當我門在nums1中隨便劃分锹引，確定nums1中左邊元素個數(shù)時（）矗钟，nums2中左邊元素的個數(shù)也隨之確定()唆香，因為是在nums1中劃分的，為了避免超出nums2的長度范圍吨艇，都默認nums1的元素個數(shù)小于nums2（即）躬它。

因此我們可以在nums1中不停的移動，來不停劃分nums1东涡，并根據(jù)計算出來的劃分nums2冯吓，并檢驗劃分后的左邊最大值小于右邊最小值是否滿足（等價于 <= nums1[i]）倘待，如果滿足就找到了合適的劃分。就可以根據(jù)的奇偶性來計算中位數(shù)：

1. 為偶數(shù)组贺，返回左邊最大值和右邊最小值的平均值凸舵。
2. 為奇數(shù)，返回左邊最大值失尖。

在nums1中移動啊奄，這個過程可以使用二分查找來加速，定義兩個下標掀潮，每次都取的中點菇夸，即（或，根據(jù)下標的更新方式選擇）庄新。

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

二分查找中點選取技巧

二分查找一般需要計算兩個下標的中點，通常有兩個計算方法薯鼠，

這兩種方法選擇主要和的更新方式有關择诈，主要是為了避免區(qū)間只有兩個數(shù)時，算法進入死循環(huán)出皇。

如果我們的按下面的方法更新关划，按計算抛腕，可能會死循環(huán)。比如循環(huán)迭代到時，some_contition條件滿足傲隶，這時候，下標一直停留在艾少，無法移動疚漆，算法無法終止，進入死循環(huán)奈附。

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

但是換成就沒有問題全度，這時，下標從移動到斥滤，剛好将鸵，循環(huán)結(jié)束。

同理佑颇，當按下面的方法更新時顶掉，也可能會死循環(huán)。

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

總結(jié)一句話：下標設置為中點時挑胸，中點靠右取整（分子+1）痒筒，下標設置為中點時，中點靠左取整（分子不加1）。