寻找两个正序数组的中位数

这道题题目描述很简单，但却是leetcode hard难度。如果用传统的二分查找方法来做，那么边界情况将非常多。

本题将寻找两个有序数组的中位数看作是从两个有序数组中查找第k小元素，具体讲解见：详细通俗的思路分析，多解法（解法三）。代码如下：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def getKthElement(k):
            idx1, idx2 = 0, 0
            while True:
                if idx1 == m:
                    return nums2[idx2+k-1]
                if idx2 == n:
                    return nums1[idx1+k-1]
                if k == 1:
                    return min(nums1[idx1], nums2[idx2])
                
                newidx1 = min(idx1 + k//2 -1, m-1)
                newidx2 = min(idx2 + k//2 -1, n-1)
                if nums1[newidx1] >= nums2[newidx2]:
                    k -= newidx2-idx2+1
                    idx2 = newidx2+1
                else:
                    k -= newidx1-idx1+1
                    idx1 = newidx1+1
        
        m = len(nums1)
        n = len(nums2)
        if (m+n)%2 == 1:
            return getKthElement((m+n)//2+1)
        else:
            return (getKthElement((m+n)//2) + getKthElement( (m+n)//2+1 )) / 2