如何找到两个排序数组的中位数？ (O(log(m+n)) 时间复杂度)

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

算法的时间复杂度应该为 O(log (m+n)) 。

方法一：归并排序

先将两个数组合并成一个有序数组，然后再求中位数。

时间复杂度：O(m+n)

方法二：二分查找

要求时间复杂度为 O(log(m+n))，一般都是用二分查找来做。

对于这道题，我们需要找到第 k 小的数，其中 k 为 (m+n)/2 或 (m+n)/2+1，具体要看 m+n 的奇偶性。

假设我们要找第 k 小的数，我们可以每次循环排除掉 k/2 个数。比较两个数组的第 k/2 个数，如果 nums1[k/2-1] < nums2[k/2-1]，说明 nums1 的前 k/2 个数都不是第 k 小的数，可以排除掉；反之，则可以排除 nums2 的前 k/2 个数。这样每次循环都可以排除 k/2 个数，直到找到第 k 小的数为止。

时间复杂度：O(log(m+n))

参考代码：

# ... 代码示例 ...