用递归查找有序二维数组的方法详解

有序二维数组中的元素按一定规律有序排列，可以利用数组的有序性加速查找的速度。本文将详细讲解用递归查找有序二维数组的方法，并给出两条示例说明。

思路

二维数组可以看作是一个矩阵，有行和列两个维度。我们可以从矩阵的左下角或右上角开始，根据当前位置的值与目标值的大小关系来确定查找的方向，以此递归查找。

具体来说，从矩阵的左下角开始查找，如果当前位置的值比目标值小，则向右查找；如果当前位置的值比目标值大，则向上查找；如果相等，则返回当前位置。

类似地，从矩阵的右上角开始查找，如果当前位置的值比目标值小，则向下查找；如果当前位置的值比目标值大，则向左查找；如果相等，则返回当前位置。

示例

示例一

我们有一个二维数组如下：

[
  [1, 3, 5, 7],
  [2, 4, 6, 8],
  [9, 11, 13, 15],
  [10, 12, 14, 16]
]

我们要查找的目标值为12。

我们从左下角开始查找，当前位置为[3, 0]，对应的值为10，比目标值小，所以向右查找，当前位置为[3, 1]，对应的值为12，与目标值相等，返回当前位置[3, 1]。

示例二

我们有一个二维数组如下：

[
  [1, 3, 5],
  [2, 4, 6],
  [9, 11, 13],
  [10, 12, 14]
]

我们要查找的目标值为7。

我们从右上角开始查找，当前位置为[0, 2]，对应的值为5，比目标值小，所以向下查找，当前位置为[1, 2]，对应的值为6，比目标值小，所以向下查找，当前位置为[2, 2]，对应的值为13，比目标值大，所以向左查找，当前位置为[2, 1]，对应的值为11，比目标值大，所以向左查找，当前位置为[2, 0]，对应的值为9，比目标值小，所以向下查找，当前位置为[3, 0]，对应的值为10，比目标值小，所以向右查找，当前位置为[3, 1]，对应的值为12，比目标值大，所以向左查找，当前位置为[3, 0]，对应的值为10，比目标值小，所以向右查找，当前位置为[3, 1]，对应的值为12，与目标值相等，返回当前位置[3, 1]。

代码实现

下面是用递归实现查找的代码示例：

def searchMatrix(matrix, target):
    if not matrix:
        return False

    rows, cols = len(matrix), len(matrix[0])
    i, j = rows - 1, 0

    def _search(i, j):
        if i < 0 or j >= cols:
            return False
        if matrix[i][j] < target:
            return _search(i, j + 1)
        elif matrix[i][j] > target:
            return _search(i - 1, j)
        else:
            return True

    return _search(i, j)

以上实现用到了闭包，函数内的搜索函数可以直接访问外层函数的局部变量matrix、target、rows和cols。

总结

递归查找有序二维数组的方法可以大大提高查找速度，它的基本思路是根据当前位置的值与目标值的大小关系来确定搜索方向，以此递归查找。