4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

solution:

这个题目想一口气写好不容易。 需要考虑的细节很多。算法倒是很好理解。既然是sorted array, 那么必须用好排好的序。所以要追求 O(ln n).

代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double res;
        int l1=nums1.size();
        int l2=nums2.size();
        int total = l1 + l2;
        if(total & 0x1){ // total is odd;
            res = findKth(nums1, 0, l1, nums2, 0, l2, total/2 + 1)*1.0;
        }
        else {
            res = (findKth(nums1, 0, l1, nums2, 0, l2, total/2)  
                  + findKth(nums1, 0, l1, nums2, 0, l2, total/2 + 1))/2.0;
        }
        return res;
    }
private:    
    int findKth(vector<int>& v1, int a1, int b1, vector<int>& v2, int a2, int b2, int k){
        int x1=b1-a1;
        int x2=b2-a2;
        if(x1>x2) return findKth(v2, a2, b2, v1, a1, b1, k);
        if(x1==0) return v2[a2+k-1];
        if(k==1) return min(v1[a1], v2[a2]);
        int m=min(x1, k/2); 
        int n=k-m;
        if(v1[a1+m-1]<v2[a2+n-1]){
            return findKth(v1, a1+m, b1, v2, a2, b2, k-m);
        }
        else if(v1[a1+m-1]>v2[a2+n-1]){
            return findKth(v1, a1, b1, v2, a2+n, b2, k-n);
        }
        else {
            return v1[a1+m-1];
        }
    }    
};