【leetcode100】搜索二维矩阵
1、题目描述
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
2、初始思路
2.1 思路
先找到正确的行，再使用二分法在该行进行查找。
2.2 代码
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix)-1, len(matrix[0])-1
#print(m,n)
i = 0
while i < m:
cur = matrix[i][n]
if cur < target:
i += 1
else:
break
l, r= 0, n
while(l <= r):
mid = (l+r)//2
if matrix[i][mid] < target:
l = mid + 1
elif matrix[i][mid] > target:
r = mid - 1
else:
return True
return False