Skip to content

Binary Search in 2D Array #3240

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Sep 3, 2022
Merged

Binary Search in 2D Array #3240

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
a168414
Binary Search in 2D Array
Shashwat79802 Aug 30, 2022
090dbda
Adding JUnit test for BinarySearc2dArray and removing main function f…
Shashwat79802 Sep 2, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
74 changes: 74 additions & 0 deletions src/main/java/com/thealgorithms/searches/BinarySearch2dArray.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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};
}
}

117 changes: 117 additions & 0 deletions src/test/java/com/thealgorithms/searches/BinarySearch2dArrayTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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]);
}

}