class Solution(object):
def searchMatrix(self, mat, target):
"""
:type mat: List[List[int]]
:type target: int
:rtype: bool
"""
if len(mat) == 0 or len(mat[0]) == 0:
return False
rowNum = len(mat)
colNum = len(mat[0])
rowIndex = 0
colIndex = colNum - 1
while colIndex >= 0 and rowIndex <= rowNum - 1:
# We start off from the top right element 'a' of the matrix,
# For any element `ele`,
# 1. if ele > a, then rowIdx will increase to corresponding level, then adjust colIdx;
# 2. if ele < a, then the rowIdx is already the corresponding level, we just have to adjust colIdx.
if mat[rowIndex][colIndex] < target:
rowIndex += 1
elif mat[rowIndex][colIndex] > target:
colIndex -= 1
else:
return True
return False
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3
, return true
.