/
Search2DMatrix2.java
49 lines (43 loc) · 1.58 KB
/
Search2DMatrix2.java
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
//https://leetcode.com/problems/search-a-2d-matrix-ii/
class Solution {
// For each row, we check the possibility of the target, and then do a binary search
public boolean searchMatrix(int[][] matrix, int target) {
/*for (int[] arr: matrix) {
if (target >= arr[0] && target <= arr[arr.length - 1] && Arrays.binarySearch(arr, target) >= 0) {
return true;
}
}*/
return search(matrix, target, 0, matrix.length - 1);
}
boolean search(int[][] arr, int target, int l, int r) {
if (l > r) {
return false;
}
int mid = (l + r)/2;
//System.out.println("Searching in arr index " + mid);
if (target >= arr[mid][0] && target <= arr[mid][arr[mid].length - 1]) {
if (Arrays.binarySearch(arr[mid],target) >= 0) {
return true;
}
}
if (mid < arr.length - 1) {
if (target >= arr[mid + 1][0] && target <= arr[mid + 1][arr[mid].length - 1]) {
if (search(arr, target, mid + 1, r)) {
return true;
}
}
}
if (mid > 0) {
if (target >= arr[mid - 1][0] && target <= arr[mid - 1][arr[mid].length - 1]) {
if (search(arr, target, l, mid - 1)) {
return true;
}
}
}
if (target < arr[mid][0]) {
return search(arr, target, l, mid - 1);
} else {
return search(arr, target, mid + 1, r);
}
}
}