lc4

class Solution {
    double findMedian(const vector<int>& vec) {
        int n = vec.size();
        if (n == 0) return 0;
        if (n % 2) {
            return vec[n / 2];
        }
        return 0.5 * (vec[n / 2 - 1] + vec[n / 2]);
    }
    double findMedian(const vector<int>& v, int b, int e) {
        int n = e - b;
        if (n <= 0) return 0;
        if (n % 2) {
            return v[b + n / 2];
        }
        return 0.5 * (v[b + n / 2 - 1] + v[b + n / 2]);
    }
    double sol(const vector<int>& v1, const vector<int> v2, int b1, int e1, int b2, int e2) {
        // printf("b1:%d e1:%d b2:%d e2:%d\n", b1, e1, b2, e2);
        int n1 = (e1 - b1);
        int n2 = (e2 - b2);

        if (n1 + n2 <= 4) {
            vector<int> v;
            for (int i = b1; i < e1; ++i) v.push_back(v1[i]);
            for (int i = b2; i < e2; ++i) v.push_back(v2[i]);
            sort(v.begin(), v.end());

            int n = v.size(), nh = v.size() / 2;
            if (n % 2) return v[nh];
            return 0.5 * (v[nh - 1] + v[nh]);
        }

        if (n1 <= 2 || n2 <= 2) {
            vector<int> v;
            if (n1 <= 2) {
                for (int i = b1; i < e1; ++i) v.push_back(v1[i]);
                for (int i = b2 + ((n2 % 2) ? n2 / 2 - 1 : n2 / 2 - 2); i < b2 + n2 / 2 + 2; ++i) v.push_back(v2[i]);
            } else {
                for (int i = b2; i < e2; ++i) v.push_back(v2[i]);
                for (int i = b1 + ((n1 % 2) ? n1 / 2 - 1 : n1 / 2 - 2); i < b1 + n1 / 2 + 2; ++i) v.push_back(v1[i]);
            }

            sort(v.begin(), v.end());
            int n = v.size(), nh = v.size() / 2;
            if (n % 2) return v[nh];
            return 0.5 * (v[nh - 1] + v[nh]);
        };

        int d1 = n1 / 2 - (1 - (n1 % 2));
        int d2 = n2 / 2 - (1 - (n2 % 2));
        int d = min(d1, d2);
        // printf("d1:%d d2:%d d:%d\n", d1, d2, d);

        double m1 = findMedian(v1, b1, e1);
        double m2 = findMedian(v2, b2, e2);

        if (m1 <= m2) {
            return sol(v1, v2, b1 + d, e1, b2, e2 - d);
        } else {
            return sol(v1, v2, b1, e1 - d, b2 + d, e2);
        }
    }
public:
    double findMedianSortedArrays(vector<int>& ns1, vector<int>& ns2) {
        int n1 = ns1.size(), n2 = ns2.size();
        return sol(ns1, ns2, 0, n1, 0, n2);
    }
};