Very similar problem to median of matrix whole solution in c++ is here


#1

double Solution::findMedianSortedArrays(const vector &A, const vector &B)
{
double ans;
if(A.size()==0)
{
if(B.size()%2)
{
ans=(double)B[B.size()/2];
}
else
{
ans=(double)(B[B.size()/2]+B[B.size()/2-1])/2;
}
return ans;
}
if(B.size()==0)
{
if(A.size()%2)
{
ans=(double)A[A.size()/2];
}
else
{
ans=(double)(A[A.size()/2]+A[A.size()/2-1])/2;
}
return ans;
}
int mn,mx;

if((A.size()+B.size())%2)
{
    mn=min(A[0],B[0]);
    mx=max(A[A.size()-1],B[B.size()-1]);
    int rq=(A.size()+B.size()+1)/2;
    while(mn<mx)
    {
        int m=(mn+mx)/2;
        if(mn+mx<0)
        {
            if(abs(mn+mx)%2)
            m--;
        }
        int s=0;
        s+=(upper_bound(B.begin(),B.end(),m)-B.begin());
        s+=(upper_bound(A.begin(),A.end(),m)-A.begin());
        if(s>=rq)
        {
            //ans=m;
            mx=m;
        }
        else mn=m+1;
    }
    ans=(double)mx;
}
else
{
    mn=min(A[0],B[0]);
    mx=max(A[A.size()-1],B[B.size()-1]);
    int rq=(A.size()+B.size())/2;
    while(mn<mx)
    {
        int m=(mn+mx)/2;
        if(mn+mx<0)
        {
            if(abs(mn+mx)%2)
            m--;
        }
        int s=0;
        s+=(upper_bound(B.begin(),B.end(),m)-B.begin());
        s+=(upper_bound(A.begin(),A.end(),m)-A.begin());
        if(s>=rq)
        {
            mx=m;
        }
        else mn=m+1;
    }
    int a=mx;
    mn=min(A[0],B[0]);
    mx=max(A[A.size()-1],B[B.size()-1]);
    rq++;
    while(mn<mx)
    {
        int m=(mn+mx)/2;
        if(mn+mx<0)
        {
            if(abs(mn+mx)%2)
            m--;
        }
        int s=0;
        s+=(upper_bound(B.begin(),B.end(),m)-B.begin());
        s+=(upper_bound(A.begin(),A.end(),m)-A.begin());
        if(s>=rq)
        {
            mx=m;
        }
        else mn=m+1;
    }
    int b=mx;
    ans=(double)(a+b)/2;
}
return ans;

}