2020-10-27

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Notes:

1.调换顺序让nums1尺寸小于nums2

2.考虑nums1为空

3.binary search，设定l和r

4.nums1里设定了搜索点k1 = l+(r-l)//2，那么k2 = total_num//2 - k1

5.对比nums1[k1-1]、nums1[k1]、nums2[k2]、nums2[k2-1]，左边超出边界设定为-∞，右边设定超出边界为+无穷大

6.maxLeftX > minRightY情况下，r = min(k1,r-1)。没有r-1的话可能会因为k1==r而无限循环。同理maxLeftY > minRightX情况下，l = max(k1,l+1)。

6.上面错了，应该写

如果右边界太大，则r = k1-1

如果左边界太小，则 l = k1+1

7.循环出去的条件是 l<=r，而不是l<r。否则过不了

print(s.findMedianSortedArrays([1],[2,3]))

8.binary search取中位数细节：