leetcode-4.cc

class Solution {
public:
    // 
    int minOfNext(vector<int>& v1, vector<int>& v2, int n1, int n2, int o1, int o2) {
        if(n1 > o1 && n2 > o2) {
            return min(v1[o1],v2[o2]);
        } else if(n1 > o1) {
            return v1[o1];
        } else {
            return v2[o2];
        }
    }

    int bsKey(vector<int>& v1, vector<int>& v2, int n1, int n2, int k) {
        int k1 = k - 1; // 1
        if(n1 == 0) {
            return v2[k1];
        } 
        if(n2 == 0) {
            return v1[k1];
        }
        
        // 4: 0,1,[2],3 
        // 3: 0,[1],2
        int o1 = -1;
        int o2 = -1;
        if(k1 == 0) { // 1
            return minOfNext(v1,v2,n1,n2,o1+1,o2+1);
        } else {
            if(v1[0] > v2[n2-1]) {
                //[3,4]
                //[1,2]
                if(n2 >= k) {
                    return v2[k1];
                } else {
                    return v1[k1-n2];
                }
            } else if(v1[n1-1] < v2[0]) { // n1-1 = 1 , v2[0] = 3
                if(n1 >= k) { //
                    return v1[k1];
                } else {
                    return v2[k1-n1];
                }
            } else {
                //
                // 1, 3, 6
                // 2, 4, 6
                int c = k1; // c = 1
                while(c > 0) { // c > 0
                    // co1
                    int co1 = min(o1+c,n1-1); // -1 + 2 = 1 (0,1)  (-1+ 1 =0), 2-1 = 1 co1 = 0
                    int cadd1 = co1 - o1; // 1 - -1 = 2  // 0 - -1 = 1 , cadd1 = 1
                    while(v1[co1] > v2[o2 + 1]) { // v1[0] = 1, v1[0] = 2
                        cadd1 /= 2; // cadd = 0
                        co1 = o1 + cadd1; // co1 = -1
                        if(cadd1 <= 0) { // break
                            break;
                        }
                    }
                    if(cadd1 == 0) { // cadd1 == 0
                        if(o1 < n1 - 1 && v1[o1+1] <= v2[o2+1]) {
                            cadd1 = 1;
                        } 
                    }
                    
                    
                    o1 = min(o1 + cadd1, n1 -1); // -1 + 1 = 0, 2 - 1 = 1 , o1 = 0
                    c = k1 - (o1 + o2 + 2); // c = 0 + -1 + 2 = 1
                    
                    // co2
                    if(c > 0) {
                        int co2 = min(o2+c,n2-1); // -1 + 2 = 1 (0,1)
                        int cadd2 = co2 - o2; // 1 - -1 = 2
                        while(v2[co2] > v1[o1 + 1]) {
                            cadd2 /= 2;
                            co2 = o2 + cadd2;
                            if(cadd2 <= 0) {
                                break;
                            }
                        }
                        if(cadd2 == 0) {
                            //cadd2 = 1;
                            if(o2 < n2 - 1 && v2[o2+1] <= v1[o1+1]) {
                               cadd2 = 1;
                            } 
                        }
                        o2 = min(o2 + cadd2, n2 -1);
                        c = k1 - (o1 + o2 + 2); // c = 0 + -1 + 2 = 1
                    }
                    
                    if(c > 0) {
                        if(o1 == n1 - 1) {
                            o2 += c;
                        } else if(o2 == n2 - 1) {
                            o1 += c;
                        }
                        c = k1 - (o1 + o2 + 2); // c = 0 + -1 + 2 = 1
                    }
                    
                }
                return minOfNext(v1,v2,n1,n2,o1+1,o2+1);
            }
        }
        
        
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int na = n1 + n2;
        int nhlf = na / 2;
        if(na % 2 == 0 ) {
            // 3/ 2 = 1 (0,[1],2)
            // 4/2 = 2 : [0,[1],[2],3]  6 (0,1,[2,3],4,5)
            // [0,(1,2),3] = 2 (2,3)
            double r1 = (double)bsKey(nums1,nums2,n1,n2, nhlf+1);
            double r2 = (double)bsKey(nums1,nums2,n1,n2, nhlf);
            return (r1 + r2) / 2;
        } else {
            // 3 / 2 = 1 (2)
            return (double)bsKey(nums1,nums2,n1,n2,nhlf+1);
        }
        
    }
};