Skip to content

Commit 03a4832

Browse files
aitorfiaitorfi
authored
Add an interface for matrix search algorithms (closes TheAlgorithms#3461) (TheAlgorithms#3464)
1 parent cce1dbd commit 03a4832

3 files changed

Lines changed: 152 additions & 138 deletions

File tree

‎src/main/java/com/thealgorithms/devutils/searches/MatrixSearchAlgorithm.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package com.thealgorithms.devutils.searches;
2+
3+
/**
4+
* The common interface of most searching algorithms that search in matrixes.
5+
*
6+
* @author Aitor Fidalgo (https://github.com/aitorfi)
7+
*/
8+
public interface MatrixSearchAlgorithm {
9+
/**
10+
* @param key is an element which should be found
11+
* @param matrix is a matrix where the element should be found
12+
* @param <T> Comparable type
13+
* @return array containing the first found coordinates of the element
14+
*/
15+
<T extends Comparable<T>> int[] find(T matrix[][], T key);
16+
}

‎src/main/java/com/thealgorithms/searches/RowColumnWiseSorted2dArrayBinarySearch.java‎

Lines changed: 37 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -1,37 +1,46 @@
11
package com.thealgorithms.searches;
22

3-
// The search is for any array which is sorted row and column-wise too. For ex :
4-
// int[][] arr = { {10, 20, 30, 40},
5-
// {15, 25, 35, 45},
6-
// {18, 28, 38, 48},
7-
// {21, 31, 41, 51}
8-
// };
9-
// This array is sorted in both row and column manner.
10-
// In this two pointers are taken, the first points to the 0th row and the second one points to end column, and then the
11-
// element corresponding to the pointers placed in the array is compared with the target that either its equal, greater or
12-
// smaller than the target. If the element is equal to the target, the co-ordinates of that element is returned i.e. an
13-
// array of the two pointers will be returned, else if the target is greater than corresponding element then the pointer
14-
// pointing to the 0th row will be incremented by 1, else if the target is lesser than the corresponding element then the
15-
// pointer pointing to the end column will be decremented by 1. And if the element doesn't exist in the array, an array
16-
// {-1, -1} will be returned.
3+
import com.thealgorithms.devutils.searches.MatrixSearchAlgorithm;
174

18-
public class RowColumnWiseSorted2dArrayBinarySearch {
5+
/**
6+
* The search is for any array which is sorted row and column-wise too. For ex :
7+
* {{10, 20, 30, 40},
8+
* {15, 25, 35, 45},
9+
* {18, 28, 38, 48},
10+
* {21, 31, 41, 51}}
11+
*
12+
* This array is sorted in both row and column manner.
13+
* In this two pointers are taken, the first points to the 0th row and the second one points to end column, and then the
14+
* element corresponding to the pointers placed in the array is compared with the target that either its equal, greater or
15+
* smaller than the target. If the element is equal to the target, the co-ordinates of that element is returned i.e. an
16+
* array of the two pointers will be returned, else if the target is greater than corresponding element then the pointer
17+
* pointing to the 0th row will be incremented by 1, else if the target is lesser than the corresponding element then the
18+
* pointer pointing to the end column will be decremented by 1. And if the element doesn't exist in the array, an array
19+
* {-1, -1} will be returned.
20+
*/
21+
public class RowColumnWiseSorted2dArrayBinarySearch
22+
implements MatrixSearchAlgorithm {
1923

20-
public static int[] search(int[][] matrix, int target) {
24+
@Override
25+
public <T extends Comparable<T>> int[] find(T[][] matrix, T key) {
26+
return search(matrix, key);
27+
}
2128

22-
int rowPointer = 0; //The pointer at 0th row
23-
int colPointer = matrix.length-1; //The pointer at end column
29+
public static <T extends Comparable<T>> int[] search(T[][] matrix, T target) {
30+
int rowPointer = 0; //The pointer at 0th row
31+
int colPointer = matrix.length - 1; //The pointer at end column
2432

25-
while (rowPointer < matrix.length && colPointer >= 0){
33+
while (rowPointer < matrix.length && colPointer >= 0) {
34+
int comp = target.compareTo(matrix[rowPointer][colPointer]);
2635

27-
if (matrix[rowPointer][colPointer] == target)
28-
return new int[] {rowPointer, colPointer};
29-
30-
else if (matrix[rowPointer][colPointer] < target)
31-
rowPointer++; //Incrementing the row pointer if the target is greater
32-
else
33-
colPointer--; //Decrementing the column pointer if the target is lesser
34-
}
35-
return new int[] {-1, -1}; //The not found condition
36+
if (comp == 0) {
37+
return new int[] { rowPointer, colPointer };
38+
} else if (comp > 0) {
39+
rowPointer++; //Incrementing the row pointer if the target is greater
40+
} else {
41+
colPointer--; //Decrementing the column pointer if the target is lesser
42+
}
3643
}
44+
return new int[] { -1, -1 }; //The not found condition
45+
}
3746
}

‎src/test/java/com/thealgorithms/searches/RowColumnWiseSorted2dArrayBinarySearchTest.java‎

Lines changed: 99 additions & 110 deletions
Original file line numberDiff line numberDiff line change
@@ -1,124 +1,113 @@
11
package com.thealgorithms.searches;
22

3-
import org.junit.jupiter.api.Test;
4-
5-
import java.util.*;
6-
73
import static org.junit.jupiter.api.Assertions.assertEquals;
84

5+
import org.junit.jupiter.api.Test;
96

107
public class RowColumnWiseSorted2dArrayBinarySearchTest {
118

12-
@Test
13-
// valid test case
14-
public void rowColumnSorted2dArrayBinarySearchTestMiddle() {
15-
int[][] arr = { {10, 20, 30, 40},
16-
{15, 25, 35, 45},
17-
{18, 28, 38, 48},
18-
{21, 31, 41, 51}
19-
};
20-
int target = 35;
21-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
22-
int[] expected = {1,2};
23-
System.out.println(Arrays.toString(ans));
24-
assertEquals(1, ans[0]);
25-
assertEquals(2, ans[1]);
26-
}
27-
28-
@Test
29-
// valid test case
30-
public void rowColumnSorted2dArrayBinarySearchTestSide() {
31-
int[][] arr = { {10, 20, 30, 40},
32-
{15, 25, 35, 45},
33-
{18, 28, 38, 48},
34-
{21, 31, 41, 51}
35-
};
36-
int target = 48;
37-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
38-
int[] expected = {2,3};
39-
System.out.println(Arrays.toString(ans));
40-
assertEquals(2, ans[0]);
41-
assertEquals(3, ans[1]);
42-
}
9+
@Test
10+
public void rowColumnSorted2dArrayBinarySearchTestMiddle() {
11+
Integer[][] arr = {
12+
{ 10, 20, 30, 40 },
13+
{ 15, 25, 35, 45 },
14+
{ 18, 28, 38, 48 },
15+
{ 21, 31, 41, 51 },
16+
};
17+
Integer target = 35;
18+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
19+
int[] expected = { 1, 2 };
20+
assertEquals(expected[0], ans[0]);
21+
assertEquals(expected[1], ans[1]);
22+
}
4323

44-
@Test
45-
// valid test case
46-
public void rowColumnSorted2dArray_BinarySearchTestUpper() {
47-
int[][] arr = { {10, 20, 30, 40},
48-
{15, 25, 35, 45},
49-
{18, 28, 38, 48},
50-
{21, 31, 41, 51}
51-
};
52-
int target = 20;
53-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
54-
int[] expected = {0,1};
55-
System.out.println(Arrays.toString(ans));
56-
assertEquals(0, ans[0]);
57-
assertEquals(1, ans[1]);
58-
}
24+
@Test
25+
public void rowColumnSorted2dArrayBinarySearchTestSide() {
26+
Integer[][] arr = {
27+
{ 10, 20, 30, 40 },
28+
{ 15, 25, 35, 45 },
29+
{ 18, 28, 38, 48 },
30+
{ 21, 31, 41, 51 },
31+
};
32+
Integer target = 48;
33+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
34+
int[] expected = { 2, 3 };
35+
assertEquals(expected[0], ans[0]);
36+
assertEquals(expected[1], ans[1]);
37+
}
5938

60-
@Test
61-
// valid test case
62-
public void rowColumnSorted2dArray_BinarySearchTestUpperSide() {
63-
int[][] arr = { {10, 20, 30, 40},
64-
{15, 25, 35, 45},
65-
{18, 28, 38, 48},
66-
{21, 31, 41, 51}
67-
};
68-
int target = 40;
69-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
70-
int[] expected = {0,3};
71-
System.out.println(Arrays.toString(ans));
72-
assertEquals(0, ans[0]);
73-
assertEquals(3, ans[1]);
74-
}
39+
@Test
40+
public void rowColumnSorted2dArray_BinarySearchTestUpper() {
41+
Integer[][] arr = {
42+
{ 10, 20, 30, 40 },
43+
{ 15, 25, 35, 45 },
44+
{ 18, 28, 38, 48 },
45+
{ 21, 31, 41, 51 },
46+
};
47+
Integer target = 20;
48+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
49+
int[] expected = { 0, 1 };
50+
assertEquals(expected[0], ans[0]);
51+
assertEquals(expected[1], ans[1]);
52+
}
7553

76-
@Test
77-
// valid test case
78-
public void rowColumnSorted2dArray_BinarySearchTestLower() {
79-
int[][] arr = { {10, 20, 30, 40},
80-
{15, 25, 35, 45},
81-
{18, 28, 38, 48},
82-
{21, 31, 41, 51}
83-
};
84-
int target = 31;
85-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
86-
int[] expected = {3,1};
87-
System.out.println(Arrays.toString(ans));
88-
assertEquals(3, ans[0]);
89-
assertEquals(1, ans[1]);
90-
}
54+
@Test
55+
public void rowColumnSorted2dArray_BinarySearchTestUpperSide() {
56+
Integer[][] arr = {
57+
{ 10, 20, 30, 40 },
58+
{ 15, 25, 35, 45 },
59+
{ 18, 28, 38, 48 },
60+
{ 21, 31, 41, 51 },
61+
};
62+
Integer target = 40;
63+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
64+
int[] expected = { 0, 3 };
65+
assertEquals(expected[0], ans[0]);
66+
assertEquals(expected[1], ans[1]);
67+
}
9168

92-
@Test
93-
// valid test case
94-
public void rowColumnSorted2dArray_BinarySearchTestLowerSide() {
95-
int[][] arr = { {10, 20, 30, 40},
96-
{15, 25, 35, 45},
97-
{18, 28, 38, 48},
98-
{21, 31, 41, 51}
99-
};
100-
int target = 51;
101-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
102-
int[] expected = {3,3};
103-
System.out.println(Arrays.toString(ans));
104-
assertEquals(3, ans[0]);
105-
assertEquals(3, ans[1]);
106-
}
69+
@Test
70+
public void rowColumnSorted2dArray_BinarySearchTestLower() {
71+
Integer[][] arr = {
72+
{ 10, 20, 30, 40 },
73+
{ 15, 25, 35, 45 },
74+
{ 18, 28, 38, 48 },
75+
{ 21, 31, 41, 51 },
76+
};
77+
Integer target = 31;
78+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
79+
int[] expected = { 3, 1 };
80+
assertEquals(expected[0], ans[0]);
81+
assertEquals(expected[1], ans[1]);
82+
}
10783

108-
@Test
109-
// valid test case
110-
public void rowColumnSorted2dArray_BinarySearchTestNotFound() {
111-
int[][] arr = { {10, 20, 30, 40},
112-
{15, 25, 35, 45},
113-
{18, 28, 38, 48},
114-
{21, 31, 41, 51}
115-
};
116-
int target = 101;
117-
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
118-
int[] expected = {-1,-1};
119-
System.out.println(Arrays.toString(ans));
120-
assertEquals(-1, ans[0]);
121-
assertEquals(-1, ans[1]);
122-
}
84+
@Test
85+
public void rowColumnSorted2dArray_BinarySearchTestLowerSide() {
86+
Integer[][] arr = {
87+
{ 10, 20, 30, 40 },
88+
{ 15, 25, 35, 45 },
89+
{ 18, 28, 38, 48 },
90+
{ 21, 31, 41, 51 },
91+
};
92+
Integer target = 51;
93+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
94+
int[] expected = { 3, 3 };
95+
assertEquals(expected[0], ans[0]);
96+
assertEquals(expected[1], ans[1]);
97+
}
12398

99+
@Test
100+
public void rowColumnSorted2dArray_BinarySearchTestNotFound() {
101+
Integer[][] arr = {
102+
{ 10, 20, 30, 40 },
103+
{ 15, 25, 35, 45 },
104+
{ 18, 28, 38, 48 },
105+
{ 21, 31, 41, 51 },
106+
};
107+
Integer target = 101;
108+
int[] ans = RowColumnWiseSorted2dArrayBinarySearch.search(arr, target);
109+
int[] expected = { -1, -1 };
110+
assertEquals(expected[0], ans[0]);
111+
assertEquals(expected[1], ans[1]);
112+
}
124113
}

0 commit comments

Comments
 (0)