用python实现二维有序数组查找。写出代码及思路

二维有序数组查找是一个常见的算法问题，可以使用双指针或二分查找的方式进行解决。下面介绍两种方法的实现。

方法一：双指针

如果二维数组是有序的，我们可以使用双指针的方式进行查找。具体的思路如下：

1. 定义两个指针row和col，分别指向二维数组的右上角。

2. 比较指针所指向的元素与目标元素的大小关系，如果相等，则返回True；如果指针所指向的元素小于目标元素，则说明目标元素在当前元素所在的列下方，将row加1；如果指针所指向的元素大于目标元素，则说明目标元素在当前元素所在的行左侧，将col减1。

3. 重复执行步骤2，直到找到目标元素或指针越界。

下面是Python代码的实现：

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1
    return False

这个函数的参数matrix是一个二维有序数组，target是要查找的目标元素。首先判断matrix是否为空，如果是则直接返回False。然后获取二维数组的行数m和列数n，将row指向0，将col指向n-1。进入循环，每次比较matrix[row][col]与target的大小关系，如果相等，则返回True。如果matrix[row][col]小于target，则说明目标元素在当前元素所在的列下方，将row加1。如果matrix[row][col]大于target，则说明目标元素在当前元素所在的行左侧，将col减1。最后如果没有找到目标元素，则返回False。

方法二：二分查找

如果二维数组的每一行都是有序的，我们可以使用二分查找的方式进行查找。具体的思路如下：

1. 对每一行进行二分查找，找到目标元素所在的行。

2. 在目标行上使用二分查找，找到目标元素。

下面是Python代码的实现：

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m - 1
    while left <= right:
        mid = (left + right) // 2
        if matrix[mid][0] <= target <= matrix[mid][n-1]:
            row = mid
            break
        elif matrix[mid][0] > target:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return False
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        if matrix[row][mid] == target:
            return True
        elif matrix[row][mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

这个函数的参数matrix是一个二维有序数组，target是要查找的目标元素。首先判断matrix是否为空，如果是则直接返回False。然后获取二维数组的行数m和列数n，将left指向0，将right指向m-1。进入循环，每次计算中间位置mid，如果matrix[mid][0]小于等于target且matrix[mid][n-1]大于等于target，则说明目标元素在第mid行，将row指向mid，跳出循环。如果matrix[mid][0]大于target，则说明目标元素在第mid行的上方，将right指向mid-1。如果matrix[mid][n-1]小于target，则说明目标元素在第mid行的下方，将left指向mid+1。最后如果没有找到目标元素，则返回False。

然后使用left指向0，使用right指向n-1，对第row行进行二分查找，判断matrix[row][mid]与target的大小关系，调整left和right的位置。最后如果找到目标元素，则返回True，否则返回False。