4. 寻找两个正序数组的中位数（困难）-二分查找

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n))

分析

• 每次排除k//2个函数，要比较两个数组所在k//2的位置的元素值，然后更新k值以及所在的索引值
• 需要判断结束条件，k == 1, 另外当其中一个数组完全被排除时候

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

        # 寻找两个正序数组的中位数，每次排除k//2个数
        # 可以不用递归
        # 传递的参数，index1和index2不断地逼近答案

        def get_kth_element(k):
            index1, index2 = 0, 0

            while True:
                if index1 == m:
                    return nums2[index2 + k - 1]
                if index2 == n:
                    return nums1[index1 + k - 1]
                
                if k == 1:
                    return min(nums1[index1], nums2[index2])
                
                new_index1 = min(index1 + k // 2 - 1, m - 1)
                new_index2 = min(index2 + k // 2 - 1, n - 1)
                tmp1 = nums1[new_index1]
                tmp2 = nums2[new_index2]

                if tmp1 < tmp2:
                    k -= new_index1 - index1 + 1
                    index1 = new_index1 + 1
                else:
                    k -= new_index2 - index2 + 1
                    index2 = new_index2 + 1
        
        m, n = len(nums1), len(nums2)
        total_len = m + n

        if total_len % 2 == 1:
            return get_kth_element((total_len + 1)//2)
        else:
            return (get_kth_element(total_len//2) + get_kth_element(total_len//2 + 1))/2