class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        auto g = [&](int x) {
            return
                (lower_bound(nums1.begin(), nums1.end(), x) - nums1.begin()) +
                (lower_bound(nums2.begin(), nums2.end(), x) - nums2.begin());
        };

        int L = -1e6, gL = 0;
        int R = +1e6, gR = g(R);
        int seek = (nums1.size() + nums2.size() + 1) / 2;
        if (gR < seek) return R;
        while (R-L > 1) {
            int M = (L+R)/2;
            int gM = g(M);
            if (gM < seek)
                L = M, gL = gM; else
                R = M, gR = gM;
        }

        if ((nums1.size() + nums2.size()) % 2 == 1)
            return L;

        if (gR >= seek+1) return L;
        auto it1 = lower_bound(nums1.begin(), nums1.end(), L+1);
        auto it2 = lower_bound(nums2.begin(), nums2.end(), L+1);
        if (it1 == nums1.end()) return (L + *it2) * 0.5;
        if (it2 == nums2.end()) return (L + *it1) * 0.5;
        return (L + min(*it1, *it2)) * 0.5;
    }
};