Skip to content

Commit 6cfb628

Browse files
Shashwat79802Shashwat79802
authored
Add Binary Search in 2D Array (TheAlgorithms#3240)
1 parent 9e37775 commit 6cfb628

File tree

2 files changed

+191
-0
lines changed

2 files changed

+191
-0
lines changed

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

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package com.thealgorithms.searches;
2+
/*
3+
To apply this method, the provided array must be strictly sorted. In this method, two pointers, one at 0th row
4+
& the other at the last row are taken & the searching is done on the basis of the middle element of the middle column.
5+
If that element is equal to target, its coordinates are returned, else if it is smaller than the target, the rows above
6+
that element are ignored (because the elements above it will also be smaller than the target), else that element is
7+
greater than the target, then the rows below it are ignored.
8+
*/
9+
public class BinarySearch2dArray
10+
{
11+
static int[] BinarySearch(int[][] arr, int target){
12+
13+
int rowCount = arr.length, colCount = arr[0].length;
14+
15+
if (rowCount == 1){
16+
return binarySearch(arr, target, 0, 0, colCount);
17+
}
18+
19+
int startRow = 0, endRow = rowCount - 1, midCol = colCount/2;
20+
21+
while (startRow < endRow - 1){
22+
23+
int midRow = startRow + (endRow - startRow) / 2; //getting the index of middle row
24+
25+
if (arr[midRow][midCol] == target){
26+
return new int[] {midRow, midCol};
27+
}
28+
else if (arr[midRow][midCol] < target)
29+
startRow = midRow;
30+
else
31+
endRow = midRow;
32+
}
33+
/*
34+
if the above search fails to find the target element, these conditions will be used to find the target
35+
element, which further uses the binary search algorithm in the places which were left unexplored.
36+
*/
37+
if (arr[startRow][midCol] == target)
38+
return new int[] {startRow, midCol};
39+
40+
if (arr[endRow][midCol] == target)
41+
return new int[] {endRow, midCol};
42+
43+
if (target <= arr[startRow][midCol-1])
44+
return binarySearch(arr, target, startRow, 0, midCol-1);
45+
46+
if (target >= arr[startRow][midCol+1] && target <= arr[startRow][colCount-1])
47+
return binarySearch(arr,target, startRow, midCol+1, colCount-1);
48+
49+
if (target <= arr[endRow][midCol-1])
50+
return binarySearch(arr, target, endRow, 0, midCol-1);
51+
52+
else
53+
return binarySearch(arr,target, endRow, midCol+1, colCount-1);
54+
}
55+
56+
static int[] binarySearch(int[][] arr, int target, int row, int colStart, int colEnd){
57+
58+
while (colStart <= colEnd){
59+
60+
int midIndex = colStart + (colEnd - colStart) / 2;
61+
62+
if (arr[row][midIndex] == target)
63+
return new int[] {row, midIndex};
64+
65+
else if (arr[row][midIndex] < target)
66+
colStart = midIndex + 1;
67+
else
68+
colEnd = midIndex - 1;
69+
}
70+
71+
return new int[] {-1, -1};
72+
}
73+
}
74+

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

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
package com.thealgorithms.searches;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import java.util.*;
6+
7+
import static org.junit.jupiter.api.Assertions.assertEquals;
8+
9+
public class BinarySearch2dArrayTest {
10+
11+
@Test
12+
// valid test case
13+
public void BinarySearch2dArrayTestMiddle() {
14+
int[][] arr = { {1, 2, 3, 4},
15+
{5, 6, 7, 8},
16+
{9,10,11,12}};
17+
int target = 6;
18+
19+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
20+
int[] expected = {1,1};
21+
System.out.println(Arrays.toString(ans));
22+
assertEquals(1, ans[0]);
23+
assertEquals(1, ans[1]);
24+
}
25+
26+
@Test
27+
// valid test case
28+
public void BinarySearch2dArrayTestMiddleSide() {
29+
int[][] arr = { {1, 2, 3, 4},
30+
{5, 6, 7, 8},
31+
{9,10,11,12}};
32+
int target = 8;
33+
34+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
35+
int[] expected = {1,3};
36+
System.out.println(Arrays.toString(ans));
37+
assertEquals(1, ans[0]);
38+
assertEquals(3, ans[1]);
39+
}
40+
41+
@Test
42+
// valid test case
43+
public void BinarySearch2dArrayTestUpper() {
44+
int[][] arr = { {1, 2, 3, 4},
45+
{5, 6, 7, 8},
46+
{9,10,11,12}};
47+
int target = 2;
48+
49+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
50+
int[] expected = {0,1};
51+
System.out.println(Arrays.toString(ans));
52+
assertEquals(0, ans[0]);
53+
assertEquals(1, ans[1]);
54+
}
55+
56+
@Test
57+
// valid test case
58+
public void BinarySearch2dArrayTestUpperSide() {
59+
int[][] arr = { {1, 2, 3, 4},
60+
{5, 6, 7, 8},
61+
{9,10,11,12}};
62+
int target = 1;
63+
64+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
65+
int[] expected = {0,0};
66+
System.out.println(Arrays.toString(ans));
67+
assertEquals(0, ans[0]);
68+
assertEquals(0, ans[1]);
69+
}
70+
71+
@Test
72+
// valid test case
73+
public void BinarySearch2dArrayTestLower() {
74+
int[][] arr = { {1, 2, 3, 4},
75+
{5, 6, 7, 8},
76+
{9,10,11,12}};
77+
int target = 10;
78+
79+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
80+
int[] expected = {2,1};
81+
System.out.println(Arrays.toString(ans));
82+
assertEquals(2, ans[0]);
83+
assertEquals(1, ans[1]);
84+
}
85+
86+
@Test
87+
// valid test case
88+
public void BinarySearch2dArrayTestLowerSide() {
89+
int[][] arr = { {1, 2, 3, 4},
90+
{5, 6, 7, 8},
91+
{9,10,11,12}};
92+
int target = 11;
93+
94+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
95+
int[] expected = {2,2};
96+
System.out.println(Arrays.toString(ans));
97+
assertEquals(2, ans[0]);
98+
assertEquals(2, ans[1]);
99+
}
100+
101+
@Test
102+
// valid test case
103+
public void BinarySearch2dArrayTestNotFound() {
104+
int[][] arr = { {1, 2, 3, 4},
105+
{5, 6, 7, 8},
106+
{9,10,11,12}};
107+
int target = 101;
108+
109+
int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
110+
int[] expected = {-1,-1};
111+
System.out.println(Arrays.toString(ans));
112+
assertEquals(-1, ans[0]);
113+
assertEquals(-1, ans[1]);
114+
}
115+
116+
}
117+

0 commit comments

Comments
 (0)