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;
}