Day 75, #5, Median of Two Sorted Arrays

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

------------------------------------------------------------------------------------------
a special case of find kth smallest
reference:
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html
http://www.programcreek.com/2012/12/leetcode-median-of-two-sorted-arrays-java/
http://blog.csdn.net/yutianzuijin/article/details/11499917
un-solved:
#1 how to determine k's value: int kA = k * lenA / (lenB + lenA)
#2 why is this inclusive: endA = kA

class Solution {
public:
    double findKth (int A[], int startA,int endA, int B[], int startB,int endB, int k) {
        int lenA = endA - startA + 1;
        int lenB = endB - startB + 1;
        if (lenA == 0) {
            return B[startB + k];
        }
        if (lenB == 0) {
            return A[startA + k];
        }
        
        if (k == 0) {
            return min(A[startA],B[startB]);
        }
        
        int kA = k * lenA / (lenB + lenA); // ???
        int kB = k - kA - 1;
        kA += startA;
        kB += startB;
        
        if (A[kA] == B[kB]) {
            return A[kA];
        }
        
        if (A[kA] > B[kB]) {
            k = k - (kB - startB + 1);
            endA = kA; // inclusive, why?
            startB = kB + 1;
            
        }else {
            k = k - (kA - startA + 1);
            startA = kA + 1; 
            endB = kB; // inclusive
        }
        
        return findKth(A,startA,endA,B,startB,endB,k);
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if ((m + n) % 2 == 1) {
            return findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2);
        }else {
            return (findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2) + findKth(A,0,m - 1,B,0,n - 1, (m + n) / 2 - 1)) / 2.0;
        }
    }
};

Solution #2, reference:  http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
如果A[i]是中位数，则A[i]比A里i 个数都大， 比B里（m+n）/2 - i 个数都大
j = (m+n)/2 - i - 1
B[j] < A[i] < B[j + 1]
反之，A在B[j]和B[j + 1]的左侧或者右侧

class Solution {
public:
    double findMedian (int A[],int B[],int m,int n,int left,int right) {
        if (left > right) {
            return findMedian(B,A,n,m,max(0,(m+n)/2 - m),min(n,(m+n)/2));
        }
        
        int i = (left + right) / 2;
        int j = (m + n) / 2 - i - 1;
        
        if (j >= 0 && A[i] < B[j]) {
            return findMedian(A,B,m,n,i + 1, right);
        }
        
        if (j < n - 1 && A[i] > B[j + 1]) {
            return findMedian(A,B,m,n,left,i - 1);
        }
        
        if ((m + n) % 2 == 1) {
            return A[i];
        }
        if (i > 0) {
            return (A[i] + max(B[j],A[i - 1])) / 2.0;
        }
        return (A[i] + B[j]) / 2.0;
        
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if (m > n) {
            return findMedian(A,B,m,n,max(0,(m+n)/2 - n),min(m,(m+n)/2));
        }
        return findMedian(B,A,n,m,max(0,(m+n)/2 - m),min(n,(m+n)/2));
    }
};

Another one, takes half of k at each call, key us (k + 1) / 2
#1 当A里的元素不足 k / 2 个时，可以砍掉B的前 k / 2
#2 当 A[k/2] < B[k/2], 可以砍掉A的前 k / 2
以上都可以用反证法证明

k为0-based

1. return B[BStart + k]意思为返回第 k + 1（1-based）小的elem
2. AK = (k + 1) / 2, 为个数，所以 k 需要 + 1
3. AStart + AK - 1, 同样道理，AK是个数（1-based），需要转换为 0-based
4. return findKth(,....AStart + AK), AK是要被砍掉的个数，所以不用 - 1

base condition以下，k和AK，BK不可能为0，所以需要 - 1，不然AStart永远取不到

http://www.ninechapter.com/solutions/median-of-two-sorted-arrays/

class Solution {
public:
    double findKth(int A[],int m, int AStart, int B[], int n, int BStart, int k) {
        if (AStart == m) return B[BStart + k];
        if (BStart == n) return A[AStart + k];
        
        if (k == 0) return min(A[AStart],B[BStart]); 
        
        int AKey = INT_MAX;
        int BKey = INT_MAX;
        int AK = (k + 1) / 2;
        int BK = (k + 1) / 2;
        
        if (AStart + AK - 1 < m) {
            AKey = A[AStart + AK - 1];
        }
        if (BStart + BK - 1 < n) {
            BKey = B[BStart + BK - 1];
        }
        
        if (AKey < BKey) {
            return findKth(A,m,AStart + AK,B,n,BStart,k - AK);
        }else {
            return findKth(A,m,AStart,B,n,BStart + BK,k - BK);
        }
        
    }

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int k = n + m;
        if (k % 2 == 0) {
            return (findKth(A,m, 0, B,n, 0, k / 2 - 1) + findKth(A,m,0, B, n, 0, k / 2)) / 2.0 ;
        } else {
            return findKth(A,m,0, B, n, 0, k / 2);
        }
    }
};