leetcode 搜索二维矩阵 II python3

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例:

现有矩阵 matrix 如下：

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

二分法搜索 矩阵已经排过序，就需要使用二分法搜索以加快我们的算法。

算法： 首先，我们确保矩阵不为空。那么，如果我们迭代矩阵对角线，从当前元素对列和行搜索，我们可以保持从当前 (row,col)(row,col) 对开始的行和列为已排序。 因此，我们总是可以二分搜索这些行和列切片。我们以如下逻辑的方式进行 : 在对角线上迭代，二分搜索行和列，直到对角线的迭代元素用完为止（意味着我们可以返回 false ）或者找到目标（意味着我们可以返回 true ）。binary search 函数的工作原理和普通的二分搜索一样,但需要同时搜索二维数组的行和列。

class Solution: def binary_search(self, matrix, target, start, vertical): lo = start hi = len(matrix[0])-1 if vertical else len(matrix)-1 while hi >= lo: mid = (lo + hi)//2 if vertical: # searching a column if matrix[start][mid] < target: lo = mid + 1 elif matrix[start][mid] > target: hi = mid - 1 else: return True else: # searching a row if matrix[mid][start] < target: lo = mid + 1 elif matrix[mid][start] > target: hi = mid - 1 else: return True return False def searchMatrix(self, matrix, target): # an empty matrix obviously does not contain `target` if not matrix: return False # iterate over matrix diagonals starting in bottom left. for i in range(min(len(matrix), len(matrix[0]))): vertical_found = self.binary_search(matrix, target, i, True) horizontal_found = self.binary_search(matrix, target, i, False) if vertical_found or horizontal_found: return True return False

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/

方法二：

''' 沿中间列从上向下搜索，直至元素大于目标值（或许碰不到，那就搜索到底），以该元素为中心，递归搜索其左下和右上矩阵，直至找到相等值。 严格注意，递归的三大条件： （1）有基本结束条件； （2）缩小规模，走向基本结束条件； （3）调用自身。 ''' class Solution: def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ if not matrix: return False def search_rec(left,up,right,down): if left>right or up>down: return False elif target<matrix[up][left] or target>matrix[down][right]: return False mid=left+(right-left)//2 row=up while row<=down and matrix[row][mid]<=target: if matrix[row][mid]==target: return True row+=1 return search_rec(left,row,mid-1,down) or search_rec(mid+1,up,right,row-1) return search_rec(0,0,len(matrix[0])-1,len(matrix)-1)