Most easy solution with proper explaination in O(logm+logn) time


#1

double Solution::findMedianSortedArrays(const vector &A, const vector &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

int n=A.size(),m=B.size();
if(n>m)
return findMedianSortedArrays(B,A);// as we are doing partition with respect to A hence all index in A will be found in B
int cut1,cut2;
int l=0,h=n;
while(l<=h){
    cut1=(l+h)/2;  // length of 1st partition
    cut2=((m+n)/2)-cut1;  // length of 2nd partition
    int l1,r1,l2,r2;
    l1=(cut1==0)?INT_MIN:A[cut1-1];
    l2=(cut2==0)?INT_MIN:B[cut2-1];
    r1=(cut1==n)?INT_MAX:A[cut1];
    r2=(cut2==m)?INT_MAX:B[cut2];
    if(l1>r2){
        h=cut1-1;
    }
    else
    if(l2>r1){
        l=cut1+1;
    }
    else{
        if((m+n)%2==0)
        return (max(l1,l2)+min(r1,r2))/2.0;
        else
        return min(r1,r2)*1.0;
        break;
    }
    }

}