二维有序数组分治法实现报错：索引越界问题调试求助

原代码的核心问题 #

1. 逻辑判断完全颠倒：
   你的矩阵是行从左到右递增、列从上到下递增的结构。从左下角出发时：
   • 若当前值小于目标，目标应该在右侧（右侧列的数更大），但原代码错误地向上移动；
   • 若当前值大于目标，目标应该在上方（上方行的数更小），原代码的分支逻辑搞反了。
2. 无边界终止条件：当递归到矩阵范围外（x<0 或 y≥列数）时，没有停止逻辑，继续访问matrix[x][y]直接触发索引越界。
3. 递归未传递返回值：每次递归调用后没有用return传递结果，就算找到目标，上层函数也无法拿到值，最终返回None。

修复后的代码 #

def KeyFinder(k, matrix, x, y):
    # 边界检查：超出矩阵范围，说明目标不存在
    if x < 0 or y >= len(matrix[0]):
        return None
    
    curr_cell = matrix[x][y]
    
    if k == curr_cell:
        return curr_cell
    elif curr_cell < k:
        # 当前值小于目标，目标在右侧，向右移动
        return KeyFinder(k, matrix, x, y + 1)
    else:
        # 当前值大于目标，目标在上方，向上移动
        return KeyFinder(k, matrix, x - 1, y)

# 测试存在的目标
var = KeyFinder(20, [[1,4,7,11], [8,9,10,20], [11,12,17,30]], 2, 0)
print(var)  # 输出 20

# 测试不存在的目标
var2 = KeyFinder(25, [[1,4,7,11], [8,9,10,20], [11,12,17,30]], 2, 0)
print(var2)  # 输出 None

修复说明 #

• 新增边界判断：一旦x或y超出矩阵合法范围，直接返回None终止递归；
• 修正逻辑分支：curr_cell < k时向右移动（y+1），curr_cell > k时向上移动（x-1）；
• 递归调用前添加return：确保找到的结果能逐层传递回初始调用。

内容的提问来源于stack exchange，提问作者Hamza