我的写法,先找到在哪一行,再找在哪一列
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
//先确定在哪一行
int first = 0, last = m-1;
while(first < last){
int mid = first + (last - first + 1) / 2;
//printf("mid = %d\n", mid);
if(matrix[mid][0] == target || matrix[mid][n-1] == target){
return true;
}else if(matrix[mid][0] > target){
last = mid-1;
//printf("last = %d\n", last);
}else{
first = mid;
}
}
int left = 0, right = n-1;
while(left < right){
int mid = (left + right) / 2;
if(matrix[first][mid] == target){
return true;
}else if(matrix[first][mid] > target){
right = mid;
}else{
left = mid + 1;
}
}
return matrix[first][left] == target;
}
};
二维数组转一维数组
行号=mid/m,列号=mid%m
二分+矩阵坐标变换
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size();
int n = matrix[0].size();
int left = 0, right = n * m - 1;
while(left < right){
int mid = (left + right) >> 1;
if(matrix[mid / n][mid % n] == target){
return true;
}else if(matrix[mid / n][mid % n] > target){
right = mid;
}else{
left = mid + 1;
}
}
return matrix[right / n][right % n] == target;
}
};