There are two sorted arrays A and B 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)).

 

思路：

难，知道用分治算法，却不知道怎么用。只好看答案。

基本的思路是如果中位数是第K个数，A[i]如果是中位数，那么A[i]已经大于了i个数，还应大于K - i - 1个数 与B[K-i-2]对比。但是如果中位数不在A中我脑子就晕晕的。下面是大神代码，我还是没有看懂。

class Solution {public:    double findMedianSortedArrays(int A[], int m, int B[], int n)    {        // the following call is to make sure len(A) <= len(B).        // yes, it calls itself, but at most once, shouldn't be        // consider a recursive solution        if (m > n)            return findMedianSortedArrays(B, n, A, m);        double ans = 0;            // now, do binary search        int k = (n + m - 1) / 2;        int l = 0, r = min(k, m); // r is n, NOT n-1, this is important!!        while (l < r) {            int midA = (l + r) / 2;            int midB = k - midA;            if (A[midA] < B[midB])                l = midA + 1;            else                r = midA;        }        // after binary search, we almost get the median because it must be between        // these 4 numbers: A[l-1], A[l], B[k-l], and B[k-l+1]         // if (n+m) is odd, the median is the larger one between A[l-1] and B[k-l].        // and there are some corner cases we need to take care of.        int a = max(l > 0 ? A[l - 1] : -(1<<30), k - l >= 0 ? B[k - l] : -(1<<30));        if (((n + m) & 1) == 1)            return (double) a;        // if (n+m) is even, the median can be calculated by         //      median = (max(A[l-1], B[k-l]) + min(A[l], B[k-l+1]) / 2.0        // also, there are some corner cases to take care of.        int b = min(l < m ? A[l] : (1<<30), k - l + 1 < n ? B[k - l + 1] : (1<<30));        return (a + b) / 2.0;    }};