Python error: recursion exceeded maximum depth cmp

Question

I'm writing a Python program to find the target in 2D array recursively, to solve this question. I'm using a binary search method to recursively find if target exist, but it gave me this maximum recursion depth exceeded error. Any suggestions?

My code:

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

I would advise you to use tuples instead of arrays for big and small. — Tarik, May 01 '21 at 00:55
In searchUtil, first if statement should check if `big == small` — Tarik, May 01 '21 at 00:57
Do you assume the solution is on the diagonal? Otherwise, you should change the coordinates independently. — Tarik, May 01 '21 at 00:59
It means that you've reached Python's recursion limit. Try rewriting it iteratively or increase [Python's recursion limit](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it?rq=1). — Gusti Adli, May 01 '21 at 00:59
As @GustiAdli said, you hit recursion limit (stack overflow) because you keep recurring searchUtil without finding the target. — Tarik, May 01 '21 at 01:02
Since there is no reason for a proper binary search to reach the recursion limit for a problem of this size, there must be an error in your update of big and small that keeps `big >= small`, thus the recursive loop never ends. One concern is you have `midx,midy = (small[0]+big[0])/2,(small[1]+big[1])/2` which is floating point rather than integer division. This should cause an error on the following line `if matrix[midx][midy] == target:` since array indexes should integer. Try integer division i.e. use `//`. — DarrylG, May 01 '21 at 01:28
What happens if big is equal to small? Hypothetically speaking, of course, since there's no [mcve] (also there's already a binary search in bisect) — Kenny Ostrom, May 01 '21 at 02:28
I think the best that could be done is linear time complexity i.e. O(max(m, n)). However, binary learch is O(log(max(m, n))) complexity, so this algorithm is undoubtedly flawed. — DarrylG, May 01 '21 at 11:39
Posted binary search algorithm would be applicable if the matrix was ordered from min to max, but it's not. Only the individual rows and columns are ordered, not the overall matrix. — DarrylG, May 01 '21 at 15:03

Daniel Hao · Answer 1 · 2021-05-01T21:05:33.147

As @DarrylG indicated, in this case, the binary search is not applicable.
Here it would be my approach to this problem:

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)

Python error: recursion exceeded maximum depth cmp

1 Answers1