AcWing 15. 二维数组中的查找
原题链接
中等
作者:
二十七杯酒
,
2020-12-24 14:48:35
,
所有人可见
,
阅读 359
二维数组的查找
C++ 代码
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(empty(matrix) || empty(matrix[0]))return false;
int row = matrix.size(), col = matrix[0].size();
int res = 0, i = 0;
for(; i < row; i ++ ){
if(matrix[i][0] > target)break;
else if(matrix[i][col - 1] < target)continue;
else
{
res = bisearch(matrix[i], 0, col - 1, target);
if(matrix[i][res] == target)return true;
}
}
return false;
}
int bisearch(vector<int>& q, int l, int r, int target){
while(l < r){
int mid = (l + r) / 2;
if(q[mid] >= target) r = mid;
else l = mid + 1;
}
return l;
}
};
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int i = row - 1, j = 0;
while(i >= 0 && j < matrix[0].size()){
if(matrix[i][j] > target)i --;
else if(matrix[i][j] <target) j ++ ;
else return true;
}
return false;
}
};