-
Notifications
You must be signed in to change notification settings - Fork 0
/
Searcha2DMatrix.cpp
37 lines (34 loc) · 1.15 KB
/
Searcha2DMatrix.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0 or matrix[0].size() == 0)
return false;
int lb = lower_bound(matrix,target);
if(lb != matrix.size() && matrix[lb][0] == target) return true;
if(lb == 0) return false;
int row = lb - 1;
lb = lower_bound(matrix[row],target);
if(lb == matrix[row].size() or matrix[row][lb] != target) return false;
else return true;
}
int lower_bound(vector<vector<int>> &matrix,int target){
int left = 0, right = matrix.size();
while(left < right){
int middle = left + (right - left) / 2;
if(matrix[middle][0] < target) left = middle + 1;
else right = middle;
}
return left;
}
int lower_bound(vector<int> &matrix,int target){
int left = 0, right = matrix.size();
while(left < right){
int middle = left + (right - left) / 2;
if(matrix[middle] < target) left = middle + 1;
else right = middle;
}
return left;
}
};