74 Search a 2D Matrix

1. Question

Write an efficient algorithm that searches for a value in anmxnmatrix. 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
[
2
[1, 3, 5, 7],
3
[10, 11, 16, 20],
4
[23, 30, 34, 50]
5
]
Copied!
Given target=3, returntrue.

2. Implementation

(1) Binary Search
思路: 因为每一行的第一个数肯定比上一行的最后一个数大,所以matrix[0][0]到matrix[m - 1][n - 1]是严格递增的, 可以直接把matrix降成一维数组,对这个一维数组进行二分查找
1
class Solution {
2
public boolean searchMatrix(int[][] matrix, int target) {
3
if (matrix == null || matrix.length == 0) {
4
return false;
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
int start = 0, end = m * n - 1, mid = 0;
9
10
while (start <= end) {
11
mid = start + (end - start) / 2;
12
int row = mid / n;
13
int col = mid % n;
14
15
if (matrix[row][col] == target) {
16
return true;
17
}
18
else if (matrix[row][col] < target) {
19
start = mid + 1;
20
}
21
else {
22
end = mid - 1;
23
}
24
}
25
return false;
26
}
27
}
Copied!

3. Time & Space Complexity

时间复杂度O(logmn), m为matrix的行数, row为matrix的列数,空间复杂度O(1)