Repository: TheAlgorithms/Java
Pull request #3240 (2022-08-30 19:44:18)

Binary Search in 2D Array
Added the program to search for the target element using **Binary Search** in the provided **2D array**. The program is modified but uses the same approach as it is built on top of binary search.

Shashwat79802: Added JUnit test for the code.

Patch:
diff --git a/src/main/java/com/thealgorithms/searches/BinarySearch2dArray.java b/src/main/java/com/thealgorithms/searches/BinarySearch2dArray.java
new file mode 100644
index 00000000..a4616e4d
--- /dev/null
+++ b/src/main/java/com/thealgorithms/searches/BinarySearch2dArray.java
@@ -0,0 +1,74 @@
+package com.thealgorithms.searches;
+/*
+To apply this method, the provided array must be strictly sorted. In this method, two pointers, one at 0th row
+& the other at the last row are taken & the searching is done on the basis of the middle element of the middle column.
+If that element is equal to target, its coordinates are returned, else if it is smaller than the target, the rows above
+that element are ignored (because the elements above it will also be smaller than the target), else that element is
+greater than the target, then the rows below it are ignored.
+ */
+public class BinarySearch2dArray
+{
+    static int[] BinarySearch(int[][] arr, int target){
+
+        int rowCount = arr.length, colCount = arr[0].length;
+
+        if (rowCount == 1){
+            return binarySearch(arr, target, 0, 0, colCount);
+        }
+
+        int startRow = 0, endRow = rowCount - 1, midCol = colCount/2;
+
+        while (startRow < endRow - 1){
+
+            int midRow = startRow + (endRow - startRow) / 2;    //getting the index of middle row
+
+            if (arr[midRow][midCol] == target){
+                return new int[] {midRow, midCol};
+            }
+            else if (arr[midRow][midCol] < target)
+                startRow = midRow;
+            else
+                endRow = midRow;
+        }
+            /*
+            if the above search fails to find the target element, these conditions will be used to find the target
+            element, which further uses the binary search algorithm in the places which were left unexplored.
+             */
+        if (arr[startRow][midCol] == target)
+            return new int[] {startRow, midCol};
+
+        if (arr[endRow][midCol] == target)
+            return new int[] {endRow, midCol};
+
+        if (target <= arr[startRow][midCol-1])
+            return binarySearch(arr, target, startRow, 0, midCol-1);
+
+        if (target >= arr[startRow][midCol+1] && target <= arr[startRow][colCount-1])
+            return binarySearch(arr,target, startRow, midCol+1, colCount-1);
+
+        if (target <= arr[endRow][midCol-1])
+            return binarySearch(arr, target, endRow, 0, midCol-1);
+
+        else
+            return binarySearch(arr,target, endRow, midCol+1, colCount-1);
+    }
+
+    static int[] binarySearch(int[][] arr, int target, int row, int colStart, int colEnd){
+
+        while (colStart <= colEnd){
+
+            int midIndex = colStart + (colEnd - colStart) / 2;
+
+            if (arr[row][midIndex] == target)
+                return new int[] {row, midIndex};
+
+            else if (arr[row][midIndex] < target)
+                colStart = midIndex + 1;
+            else
+                colEnd = midIndex - 1;
+        }
+
+        return new int[] {-1, -1};
+    }
+}
+


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java b/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java
new file mode 100644
index 00000000..ff62c844
--- /dev/null
+++ b/src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java
@@ -0,0 +1,117 @@
+package com.thealgorithms.searches;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.*;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+public class BinarySearch2dArrayTest {
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestMiddle() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 6;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {1,1};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(1, ans[0]);
+        assertEquals(1, ans[1]);
+    }
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestMiddleSide() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 8;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {1,3};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(1, ans[0]);
+        assertEquals(3, ans[1]);
+    }
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestUpper() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 2;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {0,1};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(0, ans[0]);
+        assertEquals(1, ans[1]);
+    }
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestUpperSide() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 1;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {0,0};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(0, ans[0]);
+        assertEquals(0, ans[1]);
+    }
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestLower() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 10;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {2,1};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(2, ans[0]);
+        assertEquals(1, ans[1]);
+    }
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestLowerSide() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 11;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {2,2};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(2, ans[0]);
+        assertEquals(2, ans[1]);
+    }
+
+    @Test
+    // valid test case
+    public void BinarySearch2dArrayTestNotFound() {
+        int[][] arr = { {1, 2, 3, 4},
+                        {5, 6, 7, 8},
+                        {9,10,11,12}};
+        int target = 101;
+
+        int[] ans = BinarySearch2dArray.BinarySearch(arr, target);
+        int[] expected = {-1,-1};
+        System.out.println(Arrays.toString(ans));
+        assertEquals(-1, ans[0]);
+        assertEquals(-1, ans[1]);
+    }
+
+}
+