Divide and Conquer Approach on 2D Array

Question

I am trying to apply an effective divide and conquer approach on a 2D array that is sorted row-wise, and column-wise. Starting from the bottom left cell in the matrix, my algorithm chooses either to move one cell up or one cell to right depending on whether k is > or < than the curr_cell. However, I keep getting an error of list_indices out of range when I run this code. I'd like some help in debugging this.

The following is my code:

def KeyFinder(k, matrix, x, y):

  curr_cell = matrix[x][y] #starting at bottom left corner
  
  if k == curr_cell: 
    return curr_cell
  
  else: 
    if curr_cell < k:
        KeyFinder(k, matrix, x-1, y) #if target is less than value, it must be above us so move one up
    else:
        KeyFinder(k, matrix, x, y+1) #otherwise, move one right

var = KeyFinder(20, [[1,4,7,11], [8,9,10,20], [11,12,17,30]], 2, 0)
print(var) 

Answer 1

For the error that you see, you have to check the bounds in both direction, not to go out of your matrix. However, aprart from that your implementation has other issues like when you are calling you function recursively you are not returning the answer. I did fix it like this:

def KeyFinder(k, matrix, x, y):
    m, n  = len(matrix) , len(matrix[0]) # get you dimentions
    curr_cell = matrix[x][y] #starting at bottom left corner
    
    if k == curr_cell: 
        return curr_cell
     
    if curr_cell > k and (0 < x) :
        return KeyFinder(k, matrix, x-1, y) #if target is less than value, it must be above us so move one up
    elif (y < n - 1) :
        return KeyFinder(k, matrix, x, y+1) #otherwise, move one right

var = KeyFinder(20, [[1,4,7,11], [8,9,10,20], [11,12,17,30]], 2, 0)
print(var) 

I did not change the way you wrote to be easy for you to see the changes, however, when you get the dimension you can as well set the starting point inside the function, not in the call