题目简介：
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1 | nums1 = [1, 3] |
示例 2:
1 | nums1 = [1, 2] |
思路：
由于要求时间复杂度为O(log(m + n))，所以就不能粗暴的将两个数组直接合并再排序了。而是要用到二分的思想，看了大佬们的题解后，找到了一种还算是能理解的算法，相当于把这个问题转化成了找第 K 小的元素。
假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数。看下边一个例子。
假设我们要找第 7 小的数字。(4 + 10) / 2 = 7
我们比较两个数组的第 k/2 个数字，如果 k 是奇数，向下取整。也就是比较第 3 个数字
因为 3 < 4，所以第二个数组的1,2,3都可以排除掉，相当于排除了3个数字。
由于我们已经排除掉了 3 个数字，就是这 3 个数字一定在最前边，所以在两个新数组中，我们只需要找第 7 - 3 = 4 小的数字就可以了，也就是 k = 4。
橙色的部分表示已经去掉的数字。
此时两个数组，比较第 2 个数字，3 < 5，所以我们可以把小的那个数组中的 1 ，3 排除掉了。
我们又排除掉 2 个数字，所以现在找第 4 - 2 = 2 小的数字就可以了。此时比较两个数组中的第 k / 2 = 1 个数
此时我们要比较第 1 个数字，判断两个数组中第一个数字哪个小就可以了，虽然此时两个数相等，但是我们无论去掉哪个数组中的都行，因为去掉 1 个总会保留 1 个的，所以没有影响。
由于又去掉 1 个数字，此时我们要找第 1 小的数字，所以只需判断两个数组中第一个数字哪个小就可以了，也就是 4。
所以第 7 小的数字是 4。
我们每次都是取 k/2 的数进行比较，有时候可能会遇到数组长度小于 k/2的时候。
此时 k / 2 等于 3，而上边的数组长度是 2，我们此时将箭头指向它的末尾就可以了。这样的话，由于 2 < 3，所以就会导致上边的数组 1，2 都被排除。造成下边的情况。
由于 2 个元素被排除，所以此时 k = 5，又由于上边的数组已经空了，我们只需要返回下边的数组的第 5 个数字就可以了。
讲完例子，回到代码中，关键点就是两个数组每次是否能找到第 K / 2 个数字，如果找到了就把该值取出来，找不到就赋上一个INT_MAX，然后比较两个数组第 K/2个数字，哪个数组的第 k/2个数字小，就把该数组的前k/2个数字都排除掉，并将该数组的起始位置往后移动k/2个位置，并且k需要减去k/2,递归即可。
由于两个数组长度之和 m+n 的奇偶不确定，因此需要分情况来讨论，对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。我们分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。假如 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。
tips:
若数组的起始位置大于等于该数组的长度，说明该数组已经排除了所有元素，已为空。
若
k == 1，则只需返回两数组起始位置元素较小的那个值即可。
代码如下：
1 | class Solution { |