/
solution.py
39 lines (34 loc) · 1.1 KB
/
solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from typing import List
class Solution:
@staticmethod
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
"""
:param matrix: a 2D integers list
:param target: an integer
:return: a boolean, indicate whether matrix contains target
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
n, m = len(matrix), len(matrix[0])
start, end = 0, n * m - 1
while start + 1 < end:
mid = (start + end) // 2
x, y = mid // m, mid % m
if matrix[x][y] < target:
start = mid
else:
end = mid
x, y = start // m, start % m
if matrix[x][y] == target:
return True
x, y = end // m, end % m
if matrix[x][y] == target:
return True
return False
if __name__ == '__main__':
mySolution = Solution()
# my_matrix = [[]]
my_matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
my_target = 3
my_result = mySolution.searchMatrix(my_matrix, my_target)
print(my_result)