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

下列算法的时间复杂度为O(log (k)), k = min(m,n)。比题目要求的还要好一些。

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int *sa = m <= n ? A : B;
        int *la = m <= n ? B : A;
        const int lens = m <= n ? m: n;
        const int lenl = m <= n ? n: m;

        const int c = (lens + lenl -1) / 2;

        int ls = 0;
        int us = lens - 1;

        const bool odd = (m + n) % 2;
        double result = 0;
        if (!lens && lenl)
                result = odd ? la[c] : la[c] + la[c+1];

        while (ls <= us)
        {
                const int cs = (us + ls) / 2;
                const int cl = c - cs;

                if (sa[cs] < la[cl])
                {
                        if (ls != cs)
                                ls = cs;
                        else if (cl == 0 || sa[cs] >= la[cl-1])
                        {
                                result = sa[cs];
                                if (!odd) result += cs < (lens-1) ? min(sa[cs+1], la[cl]) : la[cl];
                                break;
                        }
                        else if (cs == us)
                        {
                                result = la[cl-1];
                                if (!odd) result += la[cl];
                                break;
                        }
                        else
                                ls = cs + 1;
                }
                else if (sa[cs] > la[cl])
                {
                        if (us != cs)
                                us = cs;
                        else if (cs == ls || la[cl] >= sa[cs-1])
                        {
                                result = la[cl];
                                if (!odd) result += cl < (lenl-1) ? min(sa[cs], la[cl+1]) : sa[cs];
                                break;
                        }
                        else
                                us = cs - 1;
                }
                else
                {
                        result = sa[cs];
                        if (!odd) result += la[cl];
                        break;
                }
        }

        return odd ? result : result / 2;
    }
};

Median of Two Sorted Arrays -- leetcode