class Solution {
public:
    double mid(vector<int>& n1, vector<int>& n2,int s1,int s2,int k)
    {
        if (n1.size() == s1)
            return n2[s2 + k - 1];
        if (n2.size() == s2)
            return n1[s1 + k - 1];
        if (1 == k)
            return min(n1[s1],n2[s2]);
        int index1 = min((int)n1.size(),s1 + k / 2) - 1;
        int index2 = min((int)n2.size(),s2 + k / 2) - 1;
        if (n1[index1] <= n2[index2])
            return mid(n1,n2,index1 + 1,s2,k - (index1 - s1 + 1));
        else
            return mid(n1,n2,s1,index2 + 1,k - (index2 - s2 + 1));
    }
    double findMedianSortedArrays(vector<int>& n1, vector<int>& n2)
    {
        if (n1.size() > n2.size())
            swap(n1, n2);
        int n = n1.size(), m = n2.size();
        return (mid(n1,n2,0,0,n + m + 1 >> 1) + mid(n1,n2,0,0,n + m + 2 >> 1)) * 0.5;
    }
};