A Python2 Solution


#1
def findMedianSortedArrays(self, A, B):
        N=len(A)
        M=len(B)
        if(M+N==1):
            return A[0] if N>0 else B[0]
        if(N==0):
            return self.findMedianSortedArrays([B[0]], B[1:])
        elif (M==0):
            return self.findMedianSortedArrays([A[0]], A[1:])
        elif((M+N)%2==0):
            C=A[0:len(A)-1] if A[-1]>=B[-1] else B[0:len(B)-1]
            t1= self.findMedianSortedArrays(C, B if A[-1]>=B[-1] else A)
            C=A[1:] if A[0]<=B[0] else B[1:]
            t2= self.findMedianSortedArrays(C, B if A[0]<=B[0] else A)
            return (t1+t2)/2.0
        s=0
        e=N-1
        while(s<=e):
            mid=(int)((e+s)/2)
            res=self.count(A[mid],B,mid,len(A)-mid-1)
            if(res==0):
                return A[mid]
            elif res<0:
                s=mid+1
            else:
                e=mid-1
        s=0
        e=M-1
        while(s<=e):
            mid=(int)((e+s)/2)
            res=self.count(B[mid],A,mid,len(B)-mid-1)
            if(res==0):
                return B[mid]
            elif res<0:
                s=mid+1
            else:
                e=mid-1
    
    def count(self,val,A,left,right):
        s=0
        e=len(A)-2
        if(val<=A[0]):
            return left-(len(A)+right)
        elif val>=A[-1]:
            return left+len(A)-right
        while(s<=e):
            mid=(int)((e+s)/2)
            if(A[mid]<=val<=A[mid+1]):
                return left+mid+1-(right +len(A)-mid-1)
            elif(A[mid]<val):
                s=mid+1
            else:
                e=mid-1