-
Notifications
You must be signed in to change notification settings - Fork 0
/
bs.cpp
65 lines (62 loc) · 2.02 KB
/
bs.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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
class Solution {
public:
bool binarySearchRow(vector<int> row, int start, int end, int target) {
if (end < start)
return false;
int mid = (start+end)/2;
if (row[mid] == target)
return true;
else if (target < row[mid]) {
return binarySearchRow(row, start, mid-1, target);
} else {
return binarySearchRow(row, mid+1, end, target);
}
}
bool binarySearchMatrix(vector<vector<int> >& matrix, int start, int end, int target) {
std::cout << "binarySeachMatrix: start, end, target " << start<<end<<target << std::endl;
if (end <= start)
return false;
int mid = (start + end) / 2;
std::cout << "mid = " << mid << std::endl;
std::cout << "front " << matrix.at(mid).front() << std::endl;
std::cout << "back " << matrix.at(mid).back() << std::endl;
std::cout << "target " << target << std::endl;
if (target < matrix.at(mid).front()) {
std::cout << "case 1" << std::endl;
return binarySearchMatrix(matrix, start, mid - 1, target);
}
else
if (target > matrix.at(mid).back()){
std::cout << "case 2" << std::endl;
return binarySearchMatrix(matrix, mid+1, end, target);
}
else {
std::cout << "case 3" << std::endl;
return binarySearchRow(matrix.at(mid), 0, matrix.at(mid).size(), target);
}
}
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int size = matrix.size();
if (size == 0) {
return false;
}
return binarySearchMatrix(matrix, 0, size, target);
}
};
int main() {
vector<vector<int> > matrix;
vector<int> row;
row.push_back(1);
matrix.push_back(row);
Solution sol;
if (sol.searchMatrix(matrix, 2))
std::cout << "T" << std::endl;
else
std::cout << "F" << std::endl;
return 0;
}