时间戳

首页 > 解决方案 > Python 错误：递归超出最大深度 cmp

python - Python 错误：递归超出最大深度 cmp

问题描述

我正在编写一个 Python 程序来递归地在 2D 数组中查找目标，以解决这个问题。我正在使用二进制搜索方法递归查找目标是否存在，但它给了我这个最大递归深度超出错误。有什么建议么？

我的代码：

def searchMatrix(self, matrix, target):
    small = [0,0]
    big = [len(matrix)-1,len(matrix[0])-1]
    return self.searchUtil(matrix,target,small,big)
    
def searchUtil(self,matrix,target,small,big):
    if big >= small:
        #find the mid target
        midx,midy = (small[0]+big[0])/2,(small[1]+big[1])/2
        if matrix[midx][midy] == target:
            return True
        #if mid is >= target, it will exclude all the element smaller than it
        if matrix[midx][midy] >= target:
            return self.searchUtil(matrix,target,[midx,0],[midx,midy-1]) or self.searchUtil(matrix,target,[0,midy],[midx-1,midy]) or self.searchUtil(matrix,target,[0,0],[midx-1,midy-1])
        else:
        #if mid is < target, it will exclude all the element bigger than it
            return self.searchUtil(matrix,target,[midx+1,0],[len(matrix)-1,midy]) or self.searchUtil(matrix,target,[0,midy+1],[midx,len(matrix[0])-1]) or self.searchUtil(matrix,target,[midx+1,midy+1],[len(matrix)-1,len(matrix[0])-1])
    else:
        return False

标签： pythonalgorithmbinary-search

解决方案

正如@DarrylG 所指出的，在这种情况下，二进制搜索不适用。
这将是我解决这个问题的方法：

def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        
        if matrix:
            row, col, width = len(matrix)-1, 0, len(matrix[0])
            
            while row>=0 and col<width:
                if matrix[row][col]==target:
                    return True
                elif matrix[row][col]>target:
                    row -= 1
                else:
                    col += 1
                    
        return False
 
#  Or this one liner:  [it passed too]
#  return any(target in row for row in matrix)

推荐阅读