两排序数组中的中位数

问题描述

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

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

解决方案

一种直观的方案为使用两路归并排序的思路，找到中位数，其时间复杂度度为O（m + n）。

对于题目要求的O(log (m+n)) 的复杂度，我们很容易想到是使用二分搜索的方式求解的。

大体思路为定义find(i, j, k)为找到nums1从i开始，nums2从j开始返回其第k个元素，find(0, 0, mid)(mid = (m + n ) / 2 + 1奇数情况，偶数时求 mid - 1,和mid处的取值的均值）即为所求。

对于find(i, j, k)的求解，

判断nums1[mid1] 和 nums2[mid2] （其中mid1 = i + k / 2 - 1, mid2 = j + k / 2 - 1）的大小

若nums1[mid1] > nums2[mid2]，证明第k大的数一定不在nums2[j:mid2]只中，因此该问题可以转化为find(i, mid2 + 1, k - (mid2 - j - 1))。

同理nums1[mid1] <= nums2[mid2]，时可以删掉nums1的前半段，问题可以转换为find(mid1 + 1, j, k - (mid1 - i - 1))。

等于时不是正好为k嘛，为何不能直接返回？

不需要注意的是可能出现nums1 或者 nums2用光的情况，因此为了保证不越界的前提下，

mid1 = min（i + k / 2，n）- 1

mid2 = min（j + k / 2，m）- 1

因此恰好相等时不一定为找到第k个元素。此时删nums1、nums2均可。

对于递归的停止条件为，k == 1时，返回min（nums1[i]， nums2[j]）

代码如下：