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 a = s1 + k / 2 > n1.size() ? INT_MAX : n1[s1 + k / 2 - 1];
        int b = s2 + k / 2 > n2.size() ? INT_MAX : n2[s2 + k / 2 - 1];
        if (a >= b) return mid(n1, n2, s1, s2 + k / 2, k - k / 2);
        else    return mid(n1, n2, s1 + k / 2, s2, k - k / 2);
    }
    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;
    }
};