LC4

class Solution {
public:
    double findMedianSortedArrays(vector<int>& ns1, vector<int>& ns2) {
        if (ns1.size() > ns2.size()) return findMedianSortedArrays(ns2, ns1);
        const int mid = (ns1.size() + ns2.size() + 1) / 2;
        const int total = ns1.size() + ns2.size();
        int lb = 0, ub = ns1.size(), cnt = ub - lb, it, step;
        int low = 0, hight = ns1.size();
        while(cnt) {
            it = lb, step = cnt / 2, it += step;
            int i = lb, j = mid - i;
            int Aleft = (i == 0 ? INT_MIN : ns1[i - 1]);
            int Aright = (i == ns1.size() ? INT_MAX : ns1[i]);
            int Bleft = (j == 0 ? INT_MIN : ns2[j - 1]);
            int Bright = (j == ns2.size() ? INT_MAX : ns2[j]);
            // printf("lb,ub,cnt:%d,%d,%d alr:%d,%d blr:%d,%d\n", lb, ub, cnt, Aleft, Aright, Bleft, Bright);
            if (Aleft <= Bright && Bleft <= Aright) {
                if (total % 2) {
                    // printf("total:%d it:%d i:%d j:%d mid:%d alr:%d,%d blr:%d,%d\n", total, it, i, j, mid, Aleft, Aright, Bleft, Bright);
                    return max(Aleft, Bleft);
                } else {
                    // printf("it:%d i:%d j:%d mid:%d alr:%d,%d blr:%d,%d\n", it, i, j, mid, Aleft, Aright, Bleft, Bright);
                    return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
                }
            } else if (Bleft > Aright) {
                cnt -= step + 1;
                lb = it + 1;
            } else {
                cnt = step;
            }
        }

        // while(cnt) {
        while(low <= hight) {
            // it = lb, step = cnt / 2, it += step;
            int i = (hight + low) / 2, j = mid - i;
            int Aleft = (i == 0 ? INT_MIN : ns1[i - 1]);
            int Aright = (i == ns1.size() ? INT_MAX : ns1[i]);
            int Bleft = (j == 0 ? INT_MIN : ns2[j - 1]);
            int Bright = (j == ns2.size() ? INT_MAX : ns2[j]);
            printf("lb,ub,cnt:%d,%d,%d alr:%d,%d blr:%d,%d\n", lb, ub, cnt, Aleft, Aright, Bleft, Bright);
            if (Aleft <= Bright && Bleft <= Aright) {
                if (total % 2) {
                    printf("total:%d it:%d i:%d j:%d mid:%d alr:%d,%d blr:%d,%d\n", total, it, i, j, mid, Aleft, Aright, Bleft, Bright);
                    return max(Aleft, Bleft);
                } else {
                    printf("it:%d i:%d j:%d mid:%d alr:%d,%d blr:%d,%d\n", it, i, j, mid, Aleft, Aright, Bleft, Bright);
                    return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
                }
            } else if (Bleft > Aright) {
                low = i + 1;
            } else {
                hight = i - 1;
            }
        }
        // printf("error. lb:%d\n", lb);
        return 0;
    }
};