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

http://www.lintcode.com/en/problem/median-of-two-sorted-arrays/

Discussion

如果是O(m+n) run time, 非常简单，merge两个stoarted array然后取中位数即可。或者用两个指针，记录第k大的元素。要求 O(log (m+n))，又是sorted array，那当然要用二分查找了。问题转换成怎么用O(log (m+n))run time找到两个sorted array的第k大元素问题。

二分查找的本质就是一次比较去掉一半的情况，那怎么一次比较就可以去掉k/2中情况呢？比较A和B的第k/2个元素，这样就可以把A或者B中的前k/2个去掉了。把大白话翻译成代码就ok了。。每一次比较的结果对下次比较的输出是起始位置的更新和k的更新。------》递归。

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector<int> A, vector<int> B) {
        // write your code here
        if(A.size() == 0 && B.size()==0)
            return 0.;
        if((A.size()+B.size())%2 == 0)
            return (findKth(A, B, 0, 0, (A.size()+B.size())/2+1)
                    +findKth(A, B, 0, 0, (A.size()+B.size())/2))/2.0;
        else
            return findKth(A, B, 0, 0, (A.size()+B.size())/2+1);

    }
private:
    double findKth(vector<int> A, vector<int> B, int startA, int startB, int k) {
        int m = A.size();
        int n = B.size();
        if(startA >= m) return B[startB+k-1];
        if(startB >= n) return A[startA+k-1];
        if(k==1) return min(A[startA], B[startB]);
        int mid = k/2;//比较A,B的第K/2个元素
        int a = startA+k/2-1<m ? A[startA+k/2-1] : INT_MAX;
        int b = startB+k/2-1<n ? B[startB+k/2-1] : INT_MAX;
        if(a < b) 
            return findKth(A, B, startA+k/2-1+1, startB, k-k/2);
        else 
            return findKth(A, B, startA, startB+k/2-1+1, k-k/2);

    }
};

上述写法很容易改成iteration，这种tail recursion的情况，要么用栈，要么直接循环，不管怎样iteration的时候都要更新状态，这里就是startA, startB, k

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector<int> A, vector<int> B) {
        if(A.empty() && B.empty()) return 0.;
        int m = A.size();
        int n = B.size();
        if((m+n) % 2 ==0 ) {
            return (findKth(A, B, (m+n)/2) + findKth(A, B, (m+n)/2 + 1)) / 2.0;
        }
        return findKth(A, B, (m+n)/2 + 1);
    }
    //find kth num in A and B starting from startA and starB, respectively.
    int findKth(vector<int> &A, vector<int> &B, int k) {
        int m = A.size();
        int n = B.size();
        int startA = 0, startB = 0;
        while(true) {
            if(startA >= m) {//all the emlements in A have been visited
                return B[startB + k -1]; //kth in B
            }
            if(startB >= n) {
                return A[startA + k - 1];
            }
            //both have available elements:
            if(k==1) return min(A[startA], B[startB]);
            //compare k/2
            int a = startA + k/2 - 1 >= m ? INT_MAX: A[startA + k/2 - 1];
            int b = startB + k/2 - 1 >= n ? INT_MAX: B[startB + k/2 - 1];
            if(a > b) { //the priouse k/2 elements in b are all smaller
               startB = startB + k/2;
            } else {
                startA  = startA + k/2;
            }
            k = k-k/2;
        }
    }
};

Follow up:

run tim 不是O(log(m+n))， 而是O(log(min(m, n)))。因为折半到有一个超出长度的时候就不折半了。