74. 搜索二维矩阵
https://leetcode-cn.com/problems/search-a-2d-matrix/
难度：中等
题目：
编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
示例：
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
分析：
凡是能通过暴力AC的题都不能算中等题...
这道题分别用暴力、贪心、二分完成
解题1.双层for循环：
class Solution: def searchMatrix(self, matrix, target): for i in matrix: for j in i: if j == target: return True elif j > target: return False return False
解题2.贪心算法：
class Solution: def searchMatrix(self, matrix, target): line = len(matrix) - 1 row = len(matrix[0]) - 1 i = j = 0 while True: if matrix[i][j] == target: return True elif i < line and matrix[i + 1][j] <= target: i += 1 elif j < row and matrix[i][j + 1] <= target: j += 1 else: return False
解题3.二分查找：
class Solution: def searchMatrix(self, matrix, target): line = len(matrix) row = len(matrix[0]) left = 0 right = line * row while left < right: i, j = divmod((left + right) // 2, row) if matrix[i][j] == target: return True if matrix[i][j] < target: left = i * row + j + 1 else: right = i * row + j return False
