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 in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Example
Consider the following matrix:
1
2
3
4
5
6
7
| [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
|
Given target = 5, return true.
Given target = 20, return false.
Solution
- Java: Best Solution O(M+N)
(Search-a-2D-Matrix2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int col = matrix[0].length;
int row = matrix.length;
int i = 0;
int j = col-1;
while(i<row && j>=0){
if(target == matrix[i][j])
return true;
if(target>matrix[i][j]){
i++;
}
else
j--;
}
return false;
}
}
|
(Search-2D-Matrix2.py) download
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
| class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix:
return False
row = len(matrix)
col = len(matrix[0])
for i in range(row):
if matrix[i][0] <= target and matrix[i][col-1] >=target:
if self.searchRow(matrix,i,target) == True:
return True
return False
def searchRow(self, matrix, row, target):
n = len(matrix[0])
l = 0
r = n-1
# Binary search
while l <= r:
m = (l+r)/2
if matrix[row][m] == target:
return True
elif matrix[row][m] > target:
r = m-1
else:
l = m+1
return False
if __name__ == "__main__":
sol = Solution()
print sol.searchMatrix([[-1,3]],-1)
|