Median of Two Sorted Arrays http://oj.leetcode.com/problems/median-of-two-sorted-arrays/ 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)).

TwoSortedArrayMedian.cpp

#include <iostream>

using namespace std;

class Solution {
public:
    int min(int a, int b)
    {
        return (a < b) ? a : b;
    }

    int max(int a, int b)
    {
        return (a < b) ? b : a;
    }

    int FindK(int A[], int m, int B[], int n, int target)
    {
        if (target == 0)
        {
            if ((m != 0) && (n != 0))
            {
                return min(A[0], B[0]);
            }
            else if (m == 0)
                return B[0];
            else if (n == 0)
                return A[0];
        }
        
        if (target >= m + n)
            return 0;

        if (m == 0)
            return (target < n) ? B[target] : 0;

        if (n == 0)
            return (target < m) ? A[target] : 0;

        int k = target;
        int sA = 0;
        int sB = 0;
        while (true)
        {
            int ka = k / 2;
            int kb = k / 2;

            if (k % 2 != 0)
            {
                if (sA + ka + 1 < m)
                    ka++;
                else if (sB + kb + 1 < n)
                    kb++;
            }

            if (k == 0)
                return min(A[sA], B[sB]);

            if (k == 1)
            {
                if (A[sA] == min(A[sA], B[sB]))
                {
                    if (sA == m - 1)
                        return B[sB];
                    else
                        return min(A[sA + 1], B[sB]);
                }
                else
                {
                    if (sB == n - 1)
                        return A[sA];
                    else
                        return min(A[sA], B[sB + 1]);
                }
            }

            if (sA == m - 1)
            {
                if (A[sA] > B[sB + k - 1])
                {
                    if (sB + k < n && A[sA] <= B[sB + k])
                        return A[sA];
                    else if (sB + k < n)
                        return B[sB + k];
                    else
                        return 0;
                }
                else
                    return B[sB + k - 1];
            }

            if (sB == n - 1)
            {
                if (B[sB] > A[sA + k - 1])
                {
                    if (sA + k < m && B[sB] <= A[sA + k])
                        return B[sB];
                    else if (sA + k < m)
                        return A[sA + k];
                    else
                        return 0;
                }
                else
                    return A[sA + k - 1];
            }
            
            int indA = (sA + ka > m - 1) ? m - 1 : sA + ka;
            int indB = (sB + kb > n - 1) ? n - 1 : sB + kb;
            if (A[indA] >= B[indB])
            {
                if (sB + kb > n - 1)
                {
                    k = k - ((n - 1) - sB);
                    sB = n - 1;
                }
                else
                {
                    k -= kb;
                    sB += kb;
                }
            }
            else
            {
                if (sA + ka > m - 1)
                {
                    k = k - ((m - 1) - sA);
                    sA = m - 1;
                }
                else
                {
                    k -= ka;
                    sA += ka;
                }
            }
        }
    }
    
    double findMedianSortedArrays(int A[], int m, int B[], int n) 
    {
        int result1 = FindK(A, m, B, n, (m + n) / 2);
        int result2 = FindK(A, m, B, n, (m + n) / 2 - 1);

        if ((m + n) % 2 != 0)
            return FindK(A, m, B, n, (m + n) / 2);
        else
            return (FindK(A, m, B, n, (m + n) / 2 - 1) + FindK(A, m, B, n, (m + n) / 2)) / 2.0;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    Solution s;

    // UT - FindK
#if 1
    {
        int test1[] = { 1, 3, 5 };
        int test2[] = { 2, 4, 6, 8 };
        int test3[] = { 1, 3, 5, 7, 9 };
        int test4[] = { 2, 4, 6, 8, 10, 12 };
        int result = 0;

        cout << "UT - FindK" << endl << endl;

        result = s.FindK(test1, 3, test2, 4, 0);
        cout << result << " -- 1" << endl;
        result = s.FindK(test1, 3, test2, 4, 1);
        cout << result << " -- 2" << endl;
        result = s.FindK(test1, 3, test2, 4, 2);
        cout << result << " -- 3" << endl;
        result = s.FindK(test1, 3, test2, 4, 3);
        cout << result << " -- 4" << endl;
        result = s.FindK(test1, 3, test2, 4, 4);
        cout << result << " -- 5" << endl;
        result = s.FindK(test1, 3, test2, 4, 5);
        cout << result << " -- 6" << endl;
        result = s.FindK(test1, 3, test2, 4, 6);
        cout << result << " -- 8" << endl;

        cout << endl;

        result = s.FindK(test2, 4, test1, 3, 0);
        cout << result << " -- 1" << endl;
        result = s.FindK(test2, 4, test1, 3, 1);
        cout << result << " -- 2" << endl;
        result = s.FindK(test2, 4, test1, 3, 2);
        cout << result << " -- 3" << endl;
        result = s.FindK(test2, 4, test1, 3, 3);
        cout << result << " -- 4" << endl;
        result = s.FindK(test2, 4, test1, 3, 4);
        cout << result << " -- 5" << endl;
        result = s.FindK(test2, 4, test1, 3, 5);
        cout << result << " -- 6" << endl;
        result = s.FindK(test2, 4, test1, 3, 6);
        cout << result << " -- 8" << endl;

        cout << endl;

        result = s.FindK(test3, 5, test4, 6, 0);
        cout << result << " -- 1" << endl;
        result = s.FindK(test3, 5, test4, 6, 1);
        cout << result << " -- 2" << endl;
        result = s.FindK(test3, 5, test4, 6, 2);
        cout << result << " -- 3" << endl;
        result = s.FindK(test3, 5, test4, 6, 3);
        cout << result << " -- 4" << endl;
        result = s.FindK(test3, 5, test4, 6, 4);
        cout << result << " -- 5" << endl;
        result = s.FindK(test3, 5, test4, 6, 5);
        cout << result << " -- 6" << endl;
        result = s.FindK(test3, 5, test4, 6, 6);
        cout << result << " -- 7" << endl;
        result = s.FindK(test3, 5, test4, 6, 7);
        cout << result << " -- 8" << endl;
        result = s.FindK(test3, 5, test4, 6, 8);
        cout << result << " -- 9" << endl;
        result = s.FindK(test3, 5, test4, 6, 9);
        cout << result << " -- 10" << endl;
        result = s.FindK(test3, 5, test4, 6, 10);
        cout << result << " -- 12" << endl;

    }
#endif

    cout << endl << "-----------------------" << endl << endl;

    // Test - findMedianSortedArrays
#if 1
    {
        int test1[] = { 1, 3, 5 };
        int test2[] = { 2, 4, 6, 8 };
        int test3[] = { 1, 3, 5, 7, 9 };
        int test4[] = { 2, 4, 6, 8, 10, 12 };
        int test5[] = { 2, 4, 6, 8 };
        int test6[] = { 5, 7 };
        int test7[] = { 3 };
        int test8[] = { 1 };
        int test9[] = { 1, 2 };
        int test10[] = { 2, 3, 4 };
        int test11[] = { 3 };
        int test12[] = { 1, 2, 4 };
        double result = 0;

        cout << "Test - findMedianSortedArrays" << endl << endl;

        result = s.findMedianSortedArrays(test1, 3, test2, 4);
        cout << result << " -- 4" << endl;

        result = s.findMedianSortedArrays(test2, 4, test4, 6);
        cout << result << " -- 6" << endl;

        result = s.findMedianSortedArrays(test5, 4, test6, 2);
        cout << result << " -- 5.5" << endl;

        result = s.findMedianSortedArrays(test7, 0, test8, 1);
        cout << result << " -- 1" << endl;

        result = s.findMedianSortedArrays(test7, 0, test9, 2);
        cout << result << " -- 1.5" << endl;

        result = s.findMedianSortedArrays(test7, 1, test9, 2);
        cout << result << " -- 2" << endl;

        result = s.findMedianSortedArrays(test8, 1, test10, 3);
        cout << result << " -- 2.5" << endl;

        result = s.findMedianSortedArrays(test10, 3, test8, 1);
        cout << result << " -- 2.5" << endl;

        result = s.findMedianSortedArrays(test9, 2, test10, 3);
        cout << result << " -- 2" << endl;

        result = s.findMedianSortedArrays(test11, 1, test12, 3);
        cout << result << " -- 2.5" << endl;
    }
#endif

    cout << endl << "-----------------------" << endl << endl;
    return 0;
}