-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
50 lines (44 loc) · 1.34 KB
/
Solution.cs
File metadata and controls
50 lines (44 loc) · 1.34 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
public class Solution
{
public bool SearchMatrix(int[][] matrix, int target)
{
int n = matrix.Length, m = matrix[0].Length;
if (target < matrix[0][0] || target > matrix[n - 1][m - 1]) return false;
for (int pos = 0; pos < Math.Max(n, m); pos++)
{
if (BinarySearch(matrix, target, pos)) return true;
}
return false;
}
bool BinarySearch(int[][] matrix, int target, int pos)
{
int n = matrix.Length, m = matrix[0].Length;
// binary search by row
if (pos < n)
{
int low = 0;
int high = Math.Min(m - 1, pos);
while (low <= high)
{
int mid = low + (high - low) / 2;
if (matrix[pos][mid] == target) return true;
if (matrix[pos][mid] < target) low = mid + 1;
else high = mid - 1;
}
}
// binary search by column
if (pos < m)
{
int low = 0;
int high = Math.Min(n - 1, pos);
while (low <= high)
{
int mid = low + (high - low) / 2;
if (matrix[mid][pos] == target) return true;
if (matrix[mid][pos] < target) low = mid + 1;
else high = mid - 1;
}
}
return false;
}
}