004 - Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).
Hide Tags
Divide and Conquer Array Binary Search
 
参照解答写的（网上流传的解答 K 是从 1 开始的，我写的时候是从 0 开始的），
虽然最后通过了，但是还没有完全消化，先贴链接和代码，回头再更新分析。

链接：
http://blog.csdn.net/yutianzuijin/article/details/11499917/
http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

另外一个思路，很精巧，大致明白，还待细琢磨：
https://leetcode.com/discuss/41621/very-concise-iterative-solution-with-detailed-explanation

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size(), n=nums2.size();
        if(!m && !n)
            return 0;

        double rst=0;
        if(m>n)
        {
              rst = (double)bsearch(nums2, 0, n-1, nums1, 0, m-1, (m+n)/2);
              if(0==((m+n)%2))
                rst = (rst + (double)bsearch(nums2, 0, n-1, nums1, 0, m-1, (m+n)/2-1))/2;
        }
        else
        {
            rst = (double)bsearch(nums1, 0, m-1, nums2, 0, n-1, (m+n)/2);
            if(0==((m+n)%2))
                rst = (rst + (double)bsearch(nums1, 0, m-1, nums2, 0, n-1, (m+n)/2-1))/2;
        }
        return rst;
    }
    
    double bsearch(vector<int>& ss, int sstart, int send, 
                    vector<int>& ll, int lstart, int lend, int k)
    {
        int slen=send-sstart+1, llen=lend-lstart+1;

        if(!slen && llen)
            return (double)(ll[k]);

        if(!llen && slen)
            return (double)(ss[k]);

        if(0==k)  //slen is >0
            return ((double)min(ss[sstart], ll[lstart]));
        
        int offset=min(slen, (k+1)/2) - 1;
        int sn=ss[sstart+offset], ln=ll[lstart+k-offset-1/*the start element*/];

        if(sn<ln)
            bsearch(ss, sstart+offset+1 /*go to next, ignore elements before it*/, send, 
                    ll, lstart, lend, 
                    k-offset-1/*reduce elements ignored, include start*/);
        else if(sn>ln)
            bsearch(ss, sstart, send, 
                    ll, lstart + (k+1)/*total amount: k+1*/ - (offset+1)/*moved in ss, reduce it*/, lend,
                    offset/*reduce elements ignored, include start*/);
        else
            return (double)sn;
    }
};

40 ms.