题目

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.

举例1

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

举例2

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

思路1：（不符合时间复杂度）归并后，找到中位数即可

这个题目的关键在时间复杂度是有要求的。需要是O(log(m+n))。如果没有这个要求，那么可以将两个排序数组利用归并排序的思路，将两个数组归并为一个数组之后，然后找到中位数即可。

java代码

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int sum = nums1.length + nums2.length;
        int j = 0;
        int k = 0;
        int[] result = new int[sum];
        for (int i = 0; i < sum; i++) {
            if (j >= nums1.length) {
                result[i] = nums2[k];
                k++;
                continue;
            }
            if (k >= nums2.length) {
                result[i] = nums1[j];
                j++;
                continue;
            }
            if (nums1[j] > nums2[k]) {
                result[i] = nums2[k];
                k++;
            } else {
                result[i] = nums1[j];
                j++;
            }
        }
        if (sum % 2 != 0) {
            return result[(sum - 1) / 2];
        } else {
            return (result[sum / 2] + result[(sum / 2) - 1]) / 2.0;
        }

    }

复杂度分析

时间复杂度：O(m+n)，不符合题目中的时间复杂度要求。但是确实最容易想到的实现思路，实现起来也比较简单。
空间复杂度：O(m+n)，需要一个额外的数组，来存储两个数组的合并后的数组。

实现思路二：递归法

看到时间复杂度的要求是O(log(m+n))，很自然的想到，可能会使用到诸如树结构，二分，递归之类的方式。因为这些方式很容易产生log的复杂度。
使用递归法，我们需要掌握一定的数学知识，但是也不是很复杂的数学知识。只需要知道中位数的定义，以及知道分类讨论法这么一个数学思想就基本可以理解下面这个算法。
接下来，我们就来看一下，如何将这个问题转换为我们比较熟悉的问题。
我们需要先知道中位数的定义：

将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

实际上很好理解，中位数就是中间那个数。当数组长度为奇数，那么正好是中间那个数。如果数组长度为偶数，中位数就是中间两个数的平均数。（实现思路一中，最后取值的时候，就是利用了这个定义）

思路一中，我们将两个数组合并成了一个数组，然后对这个合并后的数组取中位数操作。那么我们不禁要想，我们能否不合并数组，而是用其他的方式，来实现我们的目的呢？

下面描述的方法，都是基于一个重要的前提。A数组，B数组都是有序的

我们假设有A，B两个数组。A有m个元素，B有n个元素。基于中位数的定义，我们如果能够AB两个数组划分成两个部分，其中一部分的元素总是小于另一个部分的元素。那么，我们就能够很好的找到中位数了。

由于我们采用不合并数组的方式，那么，必然我们需要将A数组，B数组分别分成两个部分。对于A，由于它有m个元素，所以有m+1种分法。同样，B有n个元素，就有n+1中分法。

对于A的分法，我们可以表示为A[i]，表示的是，将A分为两个部分，左侧有i个元素，右侧有m-i个元素。
对于B的分法，我们可以表示为B[j]，表示的是，将B分为两个部分，左侧有j个元素，右侧有n-j个元素。

为什么我们要这么干呢，因为中位数的定义。我们只是想要构造出这样的一个场景。那就是（条件一）

i+j=m-i+n-j(左侧元素个数=右侧元素个数)，或者
i+j=m-i+n-j+1(左侧元素个数=右侧元素个数+1)。

分别对应m+n为偶数，m+n为奇数的情况。

这样，我们就将两个数组在不合并的情况下，分成了两个相等的部分。接下来，我们需要验证一个重要的指标，那就是，按照这种分法，什么时候是满足中位数条件的分法呢？
需要满足这样的条件（条件二）：

B[j−1]≤A[i] 以及 A[i−1]≤B[j]

也就是 B左侧最大值，小于A右侧最小值。 A左侧最大值，小于B右侧最小值。 这个也是符合中位数定义而需要满足的条件。

对于条件一，我们发现，i，j是未知的变量，m，n都是已知的。从数学的角度来看。知道了i的值，就可以知道j的值。
把条件一的等式变形：

i和j的关系

看到没，i和j满足这个关系，如果还同时满足条件二。那么中位数就很简单求出来了。
如果m+n为奇数：中位数就是max（A[i-1],B[j-1]）
如果m+n为偶数：中位数就是(max(A[i-1],B[j-1])+min(A[i]+B[j]))/2

通过上面这一系列转化，发现没有，我们就把这个问题转换成了这样的问题：

已知一个有序数组，查找其中某个元素的位置。
这对上面这个问题，我们有两种方案：
1、挨个查找。
2、二分法查找。

当然，这其中还有一些关于临界值的一些特定处理。这个我们就不详细说了。我们下面看一下基于二分法思路的java实现。

java代码

public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = i + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = i - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }

复杂度分析

时间复杂度：如果采用挨个查找的方式，复杂度为：O(min(m,n)).如果采用二分法。复杂度为：O(log(min(n,m)))
空间复杂度：O(1)

总结：方法二比方法一更加高效。是由于方法二利用了中位数定义，找到了i和j的关系。这样，通过i确定j的做法，就不需要针对所有元素都进行遍历操作。只需要对其中一个数组进行操作即可。这个部分节约了不少操作，提高了效率。另外，采用二分法，也是利用了数组有序这样一个特性，进一步提高效率。