Log(m)+log(n) solution


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