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
.
假设直接对矩阵元素进行二分查找的话,时间复杂度是O(m*n),事实上非常easy想到先通过查找找到相应可能存在于哪一行,然后再在那行中查找是否存在,採用最简单的直接查找这样时间复杂度仅有O(m+n),假设这两次查找再分别採用二分查找的话,时间复杂度更能够减少到O(logm+logn),以下是O(m+n)的代码:
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if(matrix.empty())
return false;
int m = matrix.size();
int n = matrix[0].size();
int i = 0, j=0;
while(i<m && target>=matrix[i][0])
i++;
i--;
if(i==-1)
return false;
while(j<n)
{
if(target == matrix[i][j])
return true;
else
j++;
}
return false;
}
};