I think I have a log(n) solution


#1

My solution tries binary search on index i in first array and then I can know how much to take from B. I know it is log n and was wondering why is the intended solution in log(n + m)

double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
    int n = A.size(), m = B.size();
    
    int lo = -1, hi = n - 1; // all values of i
    int even = ((n + m) & 1) ^ 1; // is it odd case median.

    while (lo <= hi) {
        int mid = (lo + hi) / 2; // last element taken from A
        
        int r = n - mid - 1; // total element left from A
        int needed = (n + m) / 2 - r; // all element needed from B to complement.
        // taken too much from the right of A
        
        // printf("taken up to %d with r %d and needs %d\n", mid, r, needed);
        if (needed < 0) {
            lo = mid + 1;
            continue;
        }
        // taken too little from the right of A
        if (needed > m) {
            hi = mid - 1;
            continue;
        }
        
        int i = mid;
        int j = m - needed - 1; // index of last element in B
        
        int left_max = i > -1 ? A[i] : INT_MIN;
        if (j >= 0) left_max = max(left_max, B[j]);
        
        int right_min = min(j + 1 >= m ? INT_MAX : B[j + 1], i + 1 >= n ? INT_MAX : A[i + 1]);
        // printf("%d %d\n", left_max, right_min);
        if (left_max <= right_min) {
            double median = left_max;
            if (even) {
                median += right_min;
                return median / 2;
            } else return median;
        } else {
            // we have to reupdate our indexeses.
            if (i > -1 && left_max == A[i]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
    }
    
    return -1;
}