刷LeetCode时候做的困难题，确实比简单和中等多花了很多时间啊~

4.寻找两个有序数组的中位数

给定两个大小为m和n的有序数组nums1和nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设nums1和nums2不会同时为空。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        length = len(nums1)+len(nums2)
        m,n = len(nums1),len(nums2)
        l,r = max(0,length//2-n),min(length//2,m) #这个区间很重要
        if length%2==0:
            p,q = length//2-1,length//2
        else:
            p,q = length//2,length//2
        if m==0:
            return (nums2[p]+nums2[q])/2
        if n==0:
            return (nums1[p]+nums1[q])/2
        while l<=r:
            mid1 = (l+r)//2
            mid2 = length//2-mid1
            if mid1==0:
                lmax = nums2[mid2-1]
            elif mid2==0:
                lmax = nums1[mid1-1]
            else:
                lmax = max(nums1[mid1-1],nums2[mid2-1])
            if mid1==m:
                rmin = nums2[mid2]
            elif mid2==n:
                rmin = nums1[mid1]
            else:
                rmin = min(nums1[mid1],nums2[mid2])
            if rmin>=lmax:
                return (rmin+lmax)/2 if length%2==0 else rmin
            else:
                if nums1[mid1-1]==lmax:
                    r = mid1-1
                else:
                    l = mid1+1

注：这是第一道困难题目，理解题意就花了很长时间。第一反应是排序再直接找中位数，但是两个数组归并排序到不了log(m+n)的复杂度。这个是二分查找的变形，我们将两个数组分别分成左右两部分，两个左半部分合并，两个右半部分合并。因为中位数的位置是确定的，所以只需要在nums1上找位置即可确定nums2的位置。然后就是判断左半部分最大是不是小于右半部分最小。如果小于就成功，否则根据nums1左半部分的最大是否为左半部分最大，调整下一次二分查找的区间。第一次提交错误的地方在于没有定好l,r的区间，因为这个和nums1及nums2的长度直接相关，不然会出现下标越界。