Three-Quarters Search with python


  • -1
    E
    class Solution(object):
        def searchMatrix(self, matrix, target):
            return self.search(matrix,target,0,len(matrix)-1,0,len(matrix[0])-1) if len(matrix)>0 and len(matrix[0]) else False
        
        def search(self,matrix,target,r1,r2,c1,c2):
            rm,cm=(r1+r2)/2,(c1+c2)/2
            if matrix[rm][cm]==target:return True
            if matrix[rm][cm]>target:
                return (self.search(matrix,target,r1,rm-1,c1,c2) if rm-1>=r1 else False) or (self.search(matrix,target,rm,r2,c1,cm-1) if cm-1>=c1 else False)
            else:
                return (self.search(matrix,target,r1,rm,cm+1,c2) if cm+1<=c2 else False) or (self.search(matrix,target,rm+1,r2,c1,c2) if rm+1<=r2 else False)
    

    Each recursion,we filter One-Quarter part of all, so Tn=log_3/4(m*n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.