double get(const vector<int> &A, const vector<int> &B, int rank){
int l=0, r=A.size()-1;
// int rank=(A.size()+B.size())/2;
while(r>=l){
int m=(l+r)/2;
// cout<<l<<" "<<r<<" "<<m<<endl;
int x=rank-m;
if(x<0){
r=m-1;
}
else if(x>B.size()){
l=m+1;
continue;
} else if (x==0){
if(B[x]>=A[m])return (double)A[m];
else {
r=m-1;
}
} else if(x==B.size()){
if(B[B.size()-1]<=A[m])return (double)A[m];
else {
l=m+1;
}
} else if(B[x-1]<=A[m] && B[x]>=A[m])return (double)A[m];
else if(B[x-1]>A[m])l=m+1;
else if(B[x]<A[m])r=m-1;
}
l=0,r=B.size()-1;
while(r>=l){
int m=(l+r)/2;
int x=rank-m;
if(x<0){
r=m-1;
}
else if(x>A.size()){
l=m+1;
continue;
} else if(x==0){
if(A[0]>=B[m])return (double) B[m];
else {
r=m-1;
}
} else if(x==A.size()){
if(A[A.size()-1]<=B[m])return (double)B[m];
else {
l=m+1;
}
} else if(A[x-1]<=B[m] && A[x]>=B[m])return (double)B[m];
else if(A[x-1]>B[m])l=m+1;
else if(A[x]<B[m])r=m-1;
}
}
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
if(A.size()==0){
if(B.size()%2)return (double)B[B.size()/2];
else return (double)(B[B.size()/2]+B[B.size()/2-1])/2;
}
if(B.size()==0){
if(A.size()%2)return (double)A[A.size()/2];
else return (double)(A[A.size()/2]+A[A.size()/2-1])/2;
}
if((A.size()+B.size())%2){
return get(A,B,(A.size()+B.size())/2);
} else {
double x=get(A,B,(A.size()+B.size())/2), y=get(A,B,(A.size()+B.size())/2-1);
return (x+y)/2;
}
}
