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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000

1. 用两个指针分别指向两个数组，每次比较中，指向元素更小的指针向右移动，计数加一。时间O(m+n)

2. 二分查找，比较难想到，而且边界控制条件比较恶心，没写出来。大体思路如下：

   要找到两个数组中第k个元素，可以比较A[left1+k/2-1]和B[left2+k/2-1]，前面分别有A[left1...left1+k/2-2]和A[left2...left2+k/2-2]，即k/2-1个元素，假设A[left1+k/2-1]为两者中的较小值，则比A[left1+k/2-1]小的元素最多只有A和B的前k/2-1个元素，即最多总共只有k-2个元素，因此A[left1+k/2-1]不可能是第k个元素，A[left1]到A[left1+k/2-2]也不可能是，全都可以排除，更新左节点left1=left1+k/2，并且令k值减去排除掉的数目。k为0时找到的元素即为所求。时间O(log(m+n))。