图表统计类手机网站开发/全网整合营销平台
1. 问题描述：
编写一个高效的算法来搜索 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。
2. 思路分析：
① 从题目中可以知道向右与向下的方向都是升序的，所以很自然地想到使用二分查找的思路来解决，我们可以对每一行中查找出对应的列，然后再列中查找对应的元素看是否存在，在行与列查找元素都是可以使用二分查找的方法来解决的，我们可以声明一个方法，方法中传递一个参数来表示是查找行还是列，然后进行二分查找即可
② 因为我们可以先向右查找，然后向下进行查找，对于矩阵中的每一个元素都是面临着这两种选择，所以除了使用二分查找的方法，还可以使用递归的方法，我们可以在递归的方法中判断一下，当当前递归的元素大于了target那么直接return返回到上一层然后尝试其他的元素值，我们可以写一个有返回值的递归方法，只要是往右递归与往下递归右一个成立那么说明就是找到这个target了
3. 代码如下：
二分查找：
import sys
from typing import Listclass Solution:def binarySearch(self, l: int, r: int, matrix: List[List[int]], flag: int, x: int, target: int):# 二分查找mid = 0# 设置flag表示表示在行中查找还是在列中查找if flag == 0:# 同一行中查找列while l <= r:mid = (l + r) // 2if matrix[x][mid] == target:return midelif matrix[x][mid] < target:l = mid + 1else:r = mid - 1if matrix[x][mid] > target: return mid - 1return midelse:# 同一列中查找行mid = 0while l <= r:mid = (l + r) // 2if matrix[mid][x] == target:return midelif matrix[mid][x] < target:l = mid + 1else:r = mid - 1return middef searchMatrix(self, matrix, target):if len(matrix) == 0 or len(matrix[0]) == 0: return Falsefor i in range(len(matrix)):col = self.binarySearch(0, len(matrix[0]) - 1, matrix, 0, i, target)row = self.binarySearch(0, len(matrix) - 1, matrix, 1, col, target)if matrix[row][col] == target: return Truereturn False
递归：
import sys
from typing import Listclass Solution:# 矩阵的行与列row, col, max = 0, 0, sys.maxsize""":param r: 当前递归的行的位置:param c: 当前递归的列的位置"""def dfs(self, matrix: List[List[int]], target: int, r: int, c: int):if r == self.row or c == self.col: return Falseif matrix[r][c] == self.max: return Falseif matrix[r][c] == target: return Trueif matrix[r][c] > target: return False# 对访问过的位置进行标记matrix[r][c] = self.maxright = self.dfs(matrix, target, r, c + 1)down = self.dfs(matrix, target, r + 1, c)return right or downdef searchMatrix(self, matrix, target):if len(matrix) == 0 or len(matrix[0]) == 0: return Falseself.row, self.col = len(matrix), len(matrix[0])return self.dfs(matrix, target, 0, 0)