#include <iostream>
using namespace std;
double findMedian(const vector<int> &A,const vector<int> &B, int imin, int imax){
int i = (imin+imax)/2;
int j = (A.size()+B.size())/2 - i;
// if(!i) i = 1;
// if(!j) j = 1;
// cout << "imin: " << imin << " imax: " << imax << " i: " << i << " j: " << j << endl;
if (i>0 && j < B.size() && A[i-1] > B[j]) imax = i-1;
else if(j>0 && i < A.size() && B[j-1] > A[i]) imin = i+1;
else{
// cout << "entered" << endl;
if((A.size()+B.size())%2){
if (i < A.size() && j < B.size()) return min(A[i],B[j]);
else if (i < A.size()) return A[i];
else return B[j];
}
else{
int median = 0;
if (i-1 >= 0 && j-1 >= 0) median += max(A[i-1],B[j-1]);
else if (i-1 < 0) median += B[j-1];
else median += A[i-1];
if (i < A.size() && j < B.size()) median += min(A[i],B[j]);
else if (i < A.size()) median += A[i];
else median += B[j];
return (double) median/2;
}
}
return findMedian(A,B,imin,imax);
}
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[0] >= B[B.size()-1]){
// if( (A.size() + B.size())%2){
// if(A.size() > B.size()) return A[(A.size()-B.size())/2];
// else if(A.size() < B.size()) return B[(B.size()+A.size())/2];
// else return ((double)A[A.size()-1]+B[B.size()-1])/2;
// }
// else{
// if(A.size() > B.size()) return ((double)A[(A.size()-B.size())/2]+A[(A.size()-B.size()-1)/2])/2;
// else if(A.size() < B.size()) return ((double)B[(B.size()+A.size())/2]+ B[(B.size()+A.size()-1)/2])/2;
// else return ((double)A[A.size()-1]+B[B.size()-1])/2;
// }
// }
// else if(B[0] >= A[A.size()-1]){
// if( (A.size() + B.size())%2){
// if(A.size() > B.size()) return A[(A.size()+B.size())/2];
// else if(A.size() < B.size()) return B[(B.size()-A.size())/2];
// else return ((double)A[A.size()-1]+B[B.size()-1])/2;
// }
// else{
// if(A.size() > B.size()) return ((double)A[(A.size()+B.size())/2]+A[(A.size()+B.size()-1)/2])/2;
// else if(A.size() < B.size()) return ((double)B[(B.size()-A.size())/2]+ B[(B.size()-A.size()-1)/2])/2;
// else return ((double)A[A.size()-1]+B[B.size()-1])/2;
// }
// }
// int first = A.size()/2;
// int second = B.size()/2;
if(A.size() && B.size()){
return findMedian(A,B,max((long) 0,(long) (A.size()-B.size())/2),min((long) A.size(), (long) (A.size()+B.size())/2));
}
else if(A.size()){
if(A.size()%2){
return A[A.size()/2];
}
else{
return ((double)A[A.size()/2] + A[A.size()/2 - 1])/2;
}
}
else{
if(B.size()%2){
return B[B.size()/2];
}
else{
return ((double)B[B.size()/2]+B[B.size()/2 - 1])/2;
}
}
}