74.Search a 2D Matrix
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.
首先是最容易想到的解法，对这个m*n阶的矩阵进行遍历，时间复杂度为O(m*n)，Leetcode给出的运行时间最快为12ms，最慢为20ms，性能不够稳定，代码如下:
/*solution1
Traverse the 2D matrix*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int i=0,j=0;
int row=matrix.size(),col=matrix[0].size();
for(i=0;i<row;i++)
for(j=0;j<col;j++)
if(matrix[i][j]==target)
return true;
return false;
}
};
下面开始对算法进行优化:
既然是查找，而且元素又按照一定的顺序进行排列，那就要考虑二分算法，我们发现每一行的元素都是有序的，那么对每一行进行遍历，每一行内部使用二分查找，时间复杂度为O(mlogn），见代码：
/*solution2
use binary-search in rows*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int row=matrix.size(),i=0;
int low=0,size=matrix[0].size(),high=size-1,mid=0;
for(i=0;i<row;i++){
low=0;
high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(matrix[i][mid]==target)
return true;
if(matrix[i][mid]<target)
low=mid+1;
else
high=mid-1;
}
}
return false;
}
};
提交之后发现这个算法与最快的算法还有一定差距，于是继续思考如何优化。
上面的算法是对每行进行二分查找，既然都能想到对行进行二分查找，那为何不先用二分锁定所在行，之后用二分锁定所在列，这样时间复杂度是O(log m+log n),比刚才的两个算法时间性能上有了很大的提升。代码如下:
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())
return false;
int low=0,size=matrix.size(),high=size-1,mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(matrix[mid][0]==target)
return true;
if(matrix[mid][0]>target)
high=mid-1;
else
low=mid+1;
}
int row=high;
if(row<0)
return false;
low=0;
high=matrix[0].size()-1;
mid=0;
while(low<=high){
mid=low+(high-low)/2;
if(matrix[row][mid]==target)
return true;
if(matrix[row][mid]>target)
high=mid-1;
else
low=mid+1;
}
return false;
}
};