这是Leetcode的第四题，也是第一道难度为hard的题目，大家一起来看看看大牛眼中什么叫hard吧。。。

原题：

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)).

题目的意思比较简单，就是给定两个数组，找出这两个数组“混合”后的中位数。题目之所以难是难在了对时间复杂度有要求，O(log (m+n))，从直观上讲就是对m+n个元素的数组进行二分查找所用的时间。具体到本题，一种可行的方案是对其中一个数组进行二分查找，然后没一步查找之后都根据查找结果对另一个进行二分查找，目的是将两个数组分为一小一大两部分，例如两个数组为(1,2,3,4,5,6)和(1,2,4,6)第一个查到3以后就应该查到第二个的2，这样就有了(1,2,3/4,5,6)和(1,2/4)这样的划分。即左边儿的都比右边儿的数字要小。但很明显，这种划分并不能保证两边儿的数字个数相等（如果相等，则证明找到了正确的中间位置，进而可以得出中位数），所以这种方法的时间复杂度为log(m)*log(n)=log (m+n)。大家有兴趣可以照此实现以下，本人由于时间关系就不实验了，有时间再来补上吧。

顺便说一句，大家（应该）熟悉的归并排序也可以处理这个问题，但时间复杂度为O(m+n)，但实现思路很简单，甚至可以直接利用标准库的函数，所以实际工作中如果数据量不是很大，可以用一下归并排序的方法。

下面直接来说一个大神的解题思路和代码，其创新性的研究成果使我们有了处理该问题的利器。

（在这里感谢stellari的分享，这原解答的地址https://leetcode.com/discuss/41621/very-concise-iterative-solution-with-detailed-explanation）

大神的思路比较复杂，听我慢慢道来。。。

（1）首先是划分位置的概念。划分位置的关系我们在前面已经用过了，这是一种思想上的小转变，即将中位数看做一个划分位置。如果数组为(1,2,3,4,5)，那显然划分位置为3的位置，中位数也自然而然的落在了3的头上。如果数组为(1,2,3,4,5,6)这样的偶数组（我起的名字，大家应该都理解），那划分位置应该在3、4之间。即(1,2,3/4,5,6)(简记为(3/4))，这样一来中位数就成了(3+4)/2=3.5。至于利用划分方法找中位数的好处我们一会儿会说明。

（2）其次是两个划分位置的关系。根据题目要求要找到两个数组中所有数字的中位数，正如前面提到的，我们不妨这样考虑问题：划分的结果是把两个数组各划分成两部分，即划分结果为A1/A2，B1/B2（这里用A、B表示两个数组）。且满足A1+B1=A2+B2（中位数的概念）。显然这就是两个划分位置的关系，简单说来就是左边儿的数子个数的和与右边儿数字个数和相同，而划分位置的下标也有类似关系，这样我们知道了一个下标就可以直接求出另一个下标（这就是时间复杂度减少的原因，因为确定一个下标后另一个可以直接得到而不用再查找了）。

（3）下标问题。首先让我们清理一下思路，我们是这样处理问题的，首先对其中一个数组做二分查找，在查找过程中根据A1+B1=A2+B2来确定另一个数组的划分位置，确定以后判断是否满足左边儿的都比右边儿的数字要小（记为“条件”），如果满足证明这是正确的划分，如果不满足则根据情况来移动第一个划分位置，直到结果满足。让我们回到下标的问题，下标的问题实质就是将A1+B1=A2+B2用计算机语言描述出来，然后根据下标来判断“条件”。那么条件怎么判断呢？自然想到通过比较划分位置附近的数字大小来解决，如果A1最后一个数字（记为L1）小于等于B2第一个数字（记为R2），即L1<=R2，同理L2<=R2时，“条件“是满足的。如果L1>R2，证明L1太小了，应将A1的划分位置右移（二分查找中为查找右半部分），A2的划分位置相应左移。现在我们可以知道，我们要通过划分位置下标来获取L1、L2、R1、R2这些数字。最后我们来说一下结果：L1=A1[N/2]，L1=A1[(N+1)/2]（N为从0开始计数时的最后一个下标，具体的归纳结果就不说了，有兴趣的可以查看原帖）。

（4）对分问题。上面的结论比较容易理解，但问题还没有结束，可以说远远没有结束。这主要是因为奇数组和偶数组的特性不同，所以在实际操作时会发现“将数组平均分成两部分”是很头疼的一件事。本人也想了很多方法，但始终没有解决，还是来说大神的思路吧。

（5）占位符的引入。为了将数组均分，我们引入占位符的概念。虽然起了一个比较专业的名字，其实原理还是很简单的。即在数组的每个数字中间加入一个空的位置（与原文一样我们用'#'来表示）。所谓空的位置就是说这个位置没有数字但是有下标。这里用个图说明一下（画的一般，各位见谅）

A数组原本为(3,5,10,12,20,31)共6个元素，通过上面这样的处理变成了13个位置，也就是说把原本为N的数组变为2N+1了，显然这肯定是一个奇数，可以用中间一个位置作为划分点，这样就可以将数组均分（位置个数平均）了，即一边儿N个位置。占位符的引入是为了解决数组均分问题。

好了，现在来看一下我们都做了些什么，有什么结论了（注意这些结论是对奇偶数组通用的）。

我们拿到两个数组后（设A元素个数为N1，B元素个数为N2），首先将其插入占位符，这样最后一个位置的下标变为了2*N。中间位置的下标固定为N。原数组的“左中位数”（即L1）可以表示为A[(N1-1)/2]，"右中位数"（即L2）可以表示为A[N1/2]（注意当N1为奇数时，L1=L2）。当然还有最后一个重要结论是A1+B1（指位置）=N1+N2。

总之，我们利用占位符将数组均分，利用划分思想来表达四个关键数字（L1、R1、L2、R2）。这些都是为编程做的准备。在此之前我们再说两个注意点：

1）如果划分到最边缘了怎么办？例如输入为A=(1,1,1)，B=(2,2,2,2,2)。则A的最终划分应该为(1,1,1/)，为了处理这种情况，当划分位置靠近边缘时我们给L（或者R）赋值INT_MIN（或者INT_MAX）。

2）该选哪个作为主划分数组，即先划分哪个？如果先划分长的，那么可能会出现短的不够分的情况。比如讲长的分成了1个/3个，二此时短的只有1个，即划分为0个/一个后仍然不能满足A1+B1（指位置）=N1+N2的关系。所以应该划分短的，这样肯定不会出现"不够分"的情况。

说了这么多，现在来看一下实现代码吧：（再次感谢大神stellari的分享和解释）

<span style="font-size:14px;"><pre name="code" class="cpp"> double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int N1 = nums1.size();
    int N2 = nums2.size();
    if (N1 < N2) return findMedianSortedArrays(nums2, nums1);   // Make sure A2 is the shorter one.

    if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2;  // If A2 is empty

    int lo = 0, hi = N2 * 2;
    while (lo <= hi) {
        int mid2 = (lo + hi) / 2;   // Try Cut 2 
        int mid1 = N1 + N2 - mid2;  // Calculate Cut 1 accordingly

        double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2];  // Get L1, R1, L2, R2 respectively
        double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
        double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
        double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];

        if (L1 > R2) lo = mid2 + 1;     // A1's lower half is too big; need to move C1 left (C2 right)
        else if (L2 > R1) hi = mid2 - 1;    // A2's lower half too big; need to move C2 left.
        else return (max(L1,L2) + min(R1, R2)) / 2; // Otherwise, that's the right cut.
    }
    return -1;
 }</span>