LeetCode第4题，求两个数组nums1和nums2的中位数，要求对数复杂度。这个思路很清晰，就是二分。一开始想的lower_bound比较一波，算一下偏移，然后两段去掉相同数目的元素，构成一个子问题。不过实现的时候被字符串常见的边界情况和上下中位数困住了，想了好久，后来发现其实自己想复杂了，这就是一个求第k个数的问题，直接二分答案就好了。
设nums1[m1]和nums2[m2]为两个数列nums1[0..n1-1]和nums2[0..n2-1]的中位数（长度为奇数）和上中位数（长度为偶数），显然当nums1[m1] = nums2[m2]时为一个结束条件，此时按照奇偶长度判断一下即可。
当nums1[m1] < nums2[m2]时，显然m2取大了，m1取小了，此时中位数应该位于nums1[m1..n1-1]和nums2[0..m2]里面，注意中位数仍然可能取m2的，例如nums1 = [1, 2, 3, 4]、nums2 = [1, 3, 4]的情况，同理中位数也仍然可能取m1。但是如果单独拿出这两个片段来更新，仍然得不到子问题，因为中位数虽然在这两个片段内，但是这两个片段的中位数并不一定等于原数组的中位数。因此产生了两种想法：第一种做法试图去掉相等数量的最小值和最大值，形成依然“对称”的数组；另一种做法是不追求切完的数列依然对称，而是直接记录去掉了多少个最小值，因而新的数列中还需要去掉多少个最小值，实际上转化为求第k个小数的问题。在实现上第二种方法是高效而简单的。
对于第一种方法。假定nums1[m1] < nums2[m2]，令j = lower_bound(nums2, nums2 + n2, nums1[m1])，其中lower_bound二分搜索可以使用python中的bisect.bisect_left代替，显然j < m1，所以如果按照(m1, j)来分割，则小端变少了m2 - j个，因此nums2的分割点应该位于[j + 1, m2 - 1]这个区间内。同理，令i = upper_bound(nums1, nums1 + n1, nums2[n2])，nums1分割点应该在[m1 + 1, i - 1]这个区间内。
一个比较简单的想法是，分别对于两个数列直接去掉min(n1, n2) / 2个元素，这样是为了保证两个数组都有足够的元素可以取。此外要注意min(n1, n2) / 2 == 0的情况程序会陷入无限递归的情况，这是由于某一个数组的长度为1导致的，所以预先判定下数组长度为1的情况，写下来代码是这样的
但是这样会WA，Leetcode可以直接告诉你哪一个点WA了，于是发现对于数据[1, 4], [2, 3]是不正确的。其实这个程序每次去掉的未必是最小的数，因为最小的数未必在中位数小的数列中。
下面我们查看第二种方法，这里选择直接二分值而不是下标。对每个二分出来的值，再在两个数组中找到它的插入位置i和j，并比较i + j和k的大小，如果大了，说明中位数取大了，取左区间继续二分。
附上代码
这里注意两点，第一是lower_bound(nums1, nums1 + len, mid)始终返回是nums1中mid上确界的下标，如果mid大于nums1中所有数，下标是nums1.end()，直接取值会造成nums1越界，例如[1, 2], [3, 4]的情况。出现这种情况是因为mid取小了，而nums1整体小于nums2，lower_bound从nums1末尾借用了一个数导致下标越界。第二是两个数列中都没有mid这个数，当i + j == k时，取到的是两个数组对mid的上确界，如[1, 1, 3, 3], [1, 1, 3, 3]中第一轮取k = 4, i = 2, j = 2, mid = 2 < nums1[i] = nums2[j] = 3。
