Repository navigation
Expand file tree
/
Copy pathsearch2DMatrix.cpp
More file actions
108 lines (94 loc) · 2.8 KB
/
Copy pathsearch2DMatrix.cpp
File metadata and controls
108 lines (94 loc) · 2.8 KB
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// Source : https://oj.leetcode.com/problems/search-a-2d-matrix/
// Author : Hao Chen
// Date : 2014-06-23
/**********************************************************************************
*
* Write an efficient algorithm that searches for a value in an m x n matrix.
* This matrix has the following properties:
*
* Integers in each row are sorted from left to right.
* The first integer of each row is greater than the last integer of the previous row.
*
* For example,
*
* Consider the following matrix:
*
* [
* [1, 3, 5, 7],
* [10, 11, 16, 20],
* [23, 30, 34, 50]
* ]
*
* Given target = 3, return true.
*
**********************************************************************************/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
return searchMatrix01(matrix, target);
return searchMatrix02(matrix, target);
}
//Just simply convert the 2D matrix to 1D array.
bool searchMatrix01(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
int col = row>0 ? matrix[0].size() : 0;
int len = row * col;
int low = 0, high = len -1;
while (low <= high) {
int mid = low + (high - low) / 2;
int r = mid / col;
int c = mid % col;
int n = matrix[r][c];
if (n == target) return true;
if (n < target) low = mid+1;
else high = mid -1;
}
return false;
}
bool searchMatrix02(vector<vector<int> > &matrix, int target) {
int idx = vertical_binary_search(matrix, target);
if (idx<0){
return false;
}
idx = binary_search(matrix[idx], target);
return (idx < 0 ? false : true);
}
int vertical_binary_search(vector< vector<int> > v, int key){
int low = 0;
int high = v.size()-1;
while(low <= high){
int mid = low + (high-low)/2;
if (v[mid][0] == key){
return mid;
}
if (key < v[mid][0]){
high = mid - 1;
continue;
}
if (key > v[mid][0]){
low = mid + 1;
continue;
}
}
return low-1;
}
int binary_search(vector<int> v, int key) {
int low = 0;
int high = v.size()-1;
while(low <= high){
int mid = low + (high-low)/2;
if (v[mid] == key){
return mid;
}
if (key < v[mid]){
high = mid - 1;
continue;
}
if (key > v[mid]){
low = mid + 1;
continue;
}
}
return -1;
}
};