二维阵列的分治方法

Question

我正在尝试对按行和按列排序的2D数组应用有效的分治方法。从矩阵左下角的单元格开始，我的算法选择向上移动一个单元格或向右移动一个单元格取决于k是否为>或& lt;而不是curr_cell。然而，我一直得到一个错误的list_indices out of range当我运行这段代码时。我需要一些帮助来调试这个。

下面是我的代码:

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

对于您看到的误差，您必须检查两个方向的边界，而不是超出您的矩阵。然而，除此之外，你的实现还有其他问题，比如当你递归地调用你的函数时，你没有返回答案。我确实像这样修复了它:

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) 

我并没有为了方便您查看更改而更改您编写的方式，但是，当您获得维度时，您也可以在函数内部设置起点，而不是在调用

中设置起点。

Answer 2

好的，让我们快速总结一下。你在3x4数组中搜索数字20，它是这样的

Start at matrix [2][0] = 11.
20>11, so move to [1][0] = 8.
20>8, so move to [0][0] = 1.
20>1, so move to [-1][0]

，这是你的错误，你不能在数组中达到index=-1