 moonlightshadow123
6/21/2017 - 1:42 PM

## 74. Search a 2D Matrix

1. Search a 2D Matrix
``````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:
return False
rowNum = len(mat)
colNum = len(mat)
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:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row. For example,

Consider the following matrix:

``````[
[1,   3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
``````

Given target = `3`, return `true`.