-
Notifications
You must be signed in to change notification settings - Fork 0
/
74.cpp
38 lines (36 loc) · 1.02 KB
/
74.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
38
//combination of binary search and insert position
//12ms runtime
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(matrix.size()==0 || matrix[0].size()==0)
{
return false;
}
int start=0,end=matrix.size()-1,ans=0;
while(start<=end)
{
int mid=(start+end)/2;
if(matrix[mid][0]==target)
return true;
else if(matrix[mid][0]<target)
ans=mid,start=mid+1;
else if(matrix[mid][0]>target)
end=mid-1;
}
start=0, end=matrix[0].size()-1;
while(start<=end)
{
int mid=(start+end)/2;
if(matrix[ans][mid]==target)
return true;
else if(matrix[ans][mid]<target)
start=mid+1;
else if(matrix[ans][mid]>target)
end=mid-1;
}
return false;
}
};