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.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
难度系数
Medium
解法一：先二分查找寻找行，而后再二分查找列
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()||matrix[0].empty())return false;
int n=matrix.size(),m=matrix[0].size();
int s=0,e=n-1;
while (s<=e){
int mid=(s+e)/2;
if(target==matrix[mid][0])return true;
else if(target<matrix[mid][0])e=mid-1;
else s=mid;
if(e-s==1){//这个条件防止死循环
if(target>=matrix[e][0])s=e;
else e=s;
}
if(s==e) break;
}
int row=s;
s=0,e=m-1;
while (s<=e){
int mid=(s+e)/2;
if(target==matrix[row][mid])return true;
else if(target<matrix[row][mid])e=mid-1;
else s=mid+1;
}
return false;
}
};解法二：先二分查找寻找行，而后再二分查找列；和上题思路一样，写法更易理解
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false; // empty
int left = 0, right = matrix.size() - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (target >= matrix[mid].front() && target <= matrix[mid].back()) break;
else if (target < matrix[mid].front()) right = mid - 1;
else left = mid + 1;
}
int row = mid;
left = 0;
right = matrix[0].size() - 1;
while (left <= right) {
mid = (left + right) / 2;
if (target == matrix[row][mid]) return true;
else if (target < matrix[row][mid]) right = mid - 1;
else left = mid + 1;
}
return false;
}
};