-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSortedMatrix.java
More file actions
99 lines (68 loc) · 2.2 KB
/
Copy pathSortedMatrix.java
File metadata and controls
99 lines (68 loc) · 2.2 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
package com.binarySearch;
import java.util.Arrays;
public class SortedMatrix {
public static void main(String[] args) {
int[][] arr = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
System.out.println(Arrays.toString(search(arr, 7)));
}
static int[] binarySearch(int[][] matrix, int row, int cStart, int cEnd, int target){
while(cStart <= cEnd){
int cMid = cStart + (cEnd - cStart)/2;
if( matrix[row][cMid] == target ){
return new int[]{row,cMid};
}
if( matrix[row][cMid] > target){
cStart = cMid + 1;
}else{
cEnd = cMid - 1;
}
}
return new int[]{-1, -1};
}
static int[] search(int[][] matrix, int target){
int row = matrix.length;
int col = matrix[0].length;
if(col == 0){
return new int[]{-1, -1};
}
if(row == 1){
return binarySearch(matrix, 0, 0, col, target);
}
int rStart = 0;
int rEnd = row - 1;
int cMid = col/2;
while(rStart < (rEnd-1)){
int mid = rStart + (rEnd - rStart)/2;
if( matrix[mid][cMid] == target){
return new int[]{mid, cMid};
}
if( matrix[mid][cMid] > target){
rEnd = mid;
}else{
rStart = mid;
}
}
// Now we have 2 rows
if(matrix[rStart][cMid] == target){
return new int[]{rStart, cMid};
}
if(matrix[rStart + 1][cMid] == target){
return new int[]{rStart, cMid};
}
if(matrix[rStart][cMid - 1 ] >= target){
return binarySearch(matrix, rStart,0 ,cMid - 1, target);
}
if(matrix[rStart][cMid + 1 ] <= target){
return binarySearch(matrix, rStart,cMid + 1 ,col - 1, target);
}
if(matrix[rStart + 1][cMid + 1 ] <= target){
return binarySearch(matrix, rStart + 1,cMid + 1 ,col - 1, target);
}else{
return binarySearch(matrix, rStart + 1,0 ,cMid - 1, target);
}
}
}