How to handle the case when (m+n) is even, if I want to solve using mathod similar to matrix median problem


#1

I was trying to solve the problem by a method similar to that used in the matrix median since two arrays can be considered as a 2*N matrix. But I don’t know how to handle the case when (m+n) i.e. the sum of the number of elements of the two array, is even. Here is my code when m+n is odd-

double Solution::findMedianSortedArrays(const vector<int> &A, const vector<int> &B) {
    // Do not write main() function.
    // Do not read input, instead use the arguments to the function.
    // Do not print the output, instead return values as specified
    // Still have a doubt. Checkout www.interviewbit.com/pages/sample_codes/ for more details

    int m = A.size();
    int n = B.size();
    
    if(m == 0){
        if(n%2 == 1){
            return double(B[n/2]);
        }
        else{
            return (B[n/2]*1.0 + B[n/2 + 1]*1.0)/2;
        }
    }
    if(n == 0){
        if(m%2 == 1){
            return double(A[m/2]);
        }
        else{
            return (A[m/2]*1.0 + A[m/2 + 1]*1.0)/2;
        }
    }
    int req = (m+n)/2;
    
    int min, max;
    
    
    min = A[0]<B[0]?A[0]:B[0];
    max = A[m-1]>B[n-1]?A[m-1]:B[n-1];
    
    
    while(min<max){
        int mid = min + (max-min)/2;
        int count = 0;
        count += upper_bound(A.begin(), A.end(), mid) - A.begin();
        count += upper_bound(B.begin(), B.end(), mid) - B.begin();
        if(count < req){
             min = mid + 1;
        }
        else{
             max = mid;
        }
    }
    return min;
}

#2

int f(int count,int s,int e,const vector &A, const vector &B){
int ans=-1;
while(s<=e){
int mid=(s+e)/2;
int c=(upper_bound(A.begin(),A.end(),mid)-A.begin())+(upper_bound(B.begin(),B.end(),mid)-B.begin());
if(c>=count){
ans=mid;
e=mid-1;
}else{
s=mid+1;
}
}
return ans;
}

double Solution::findMedianSortedArrays(const vector &A, const vector &B) {

int m=A.size(),n=B.size();
int s,e;

if(m!=0&&n!=0){
    s=min(A[0],B[0]);
    e=max(A[m-1],B[n-1]);
}
else if(m==0){
    s=(B[0]);
    e=(B[n-1]);
}else if(n==0){
    s=(A[0]);
    e=(A[m-1]);
}

if((m+n)%2==1){
    return f((m+n)/2+1,s,e,A,B);
}else{
    return ((f((m+n)/2,s,e,A,B)+f((m+n)/2+1,s,e,A,B))*1.0)/2;
}

}