Binary search 2D array - Java
I am stuck with the following question:
For a two-dimensional matrix of
mat
size n 2 where n = 2 k, find the integer k.
The rows and columns of the matrix are sorted.
If we divide the matrix into quarters, each quarter will be sorted as well. For example, given this matrix:
-4 -2 5 9 2 5 12 13 13 20 25 25 22 24 49 57
If we divide it into quarters, we can see that all the numbers in the first quarter are equal or less than the numbers in the second quarter.
To get an efficient algorithm, I thought about doing a recursive binary search in two dimensions, but it was unable to search 2
in the previous matrix.
Here's the code:
public static boolean find(int[][] mat, int x){
return find2(mat, x, 0, mat.length-1,0, mat.length-1);
}
private static boolean find2(int[][] mat, int x, int lorow, int hirow,int locol,int hicol){
if(mat.length==0) return false;
if(lorow>hirow || locol>hicol) return false;
int midrow=(lorow+hirow)/2;
int midcol=(locol+hicol)/2;
if(mat[midrow][midcol] == x ) return true;
else if(mat[midrow][midcol] < x)
return find2(mat,x,lorow,midrow,midcol+1,hicol) || find2(mat,x,midrow+1,hirow,locol,midcol) || find2(mat,x,midrow+1,hirow,midcol+1,hicol);
else
return find2(mat,x,lorow,midrow,locol,midcol-1) || find2(mat,x,midrow,hirow,locol,midcol-1) || find2(mat,x,midrow+1,hirow,midcol+1,hicol);
}
Please advise.
source to share
If your matrix row and column are sorted then you can use below code.
public int search(int mat[][], int n, int x) {
int i = 0, j = n - 1;
while (i < n && j >= 0) {
if (mat[i][j] == x) {
System.out.println("Found at" + i + j);
return 1;
}
if (mat[i][j] > x)
j--;
else // if mat[i][j] < x
i++;
}
System.out.println("not Found at");
return 0;
}
source to share
Your mistake is here in your code.
else
return find2(mat,x,lorow,midrow,locol,midcol-1) || find2(mat,x,midrow,hirow,locol,midcol-1) || find2(mat,x,midrow+1,hirow,midcol+1,hicol);
Here in the first two functions you are removing middle column
from your search space. You must enable it as the item may be present on middle column
. Another mistake is the last call find2(mat,x,midrow+1,hirow,midcol+1,hicol)
.
If your search term is smaller than the middle item, you should select the quadrant of the top-left
middle item and ignore the quadrant bottom-right
. You missed a quadrant bottom-right
within a quadrant top-left
.
After making the appropriate changes, the return function in else looks like this:
return find2(mat,x,lorow,midrow,locol,midcol) || find2(mat,x,lorow,midrow,midcol+1,hicol) ||find2(mat,x,midrow+1,hirow,locol,midcol);
This fixed the issue and returns true
for -2
.
Updated code:
private static boolean find2(int[][] mat, int x, int lorow, int hirow,int locol,int hicol){
if(mat.length==0) return false;
if(lorow>hirow || locol>hicol) return false;
if(lorow==hirow && locol==hicol && mat[lorow][locol]!=x)
return false;
int midrow=(lorow+hirow)/2;
int midcol=(locol+hicol)/2;
if(mat[midrow][midcol] == x ) return true;
else if(mat[midrow][midcol] < x)
return find2(mat,x,lorow,midrow,midcol+1,hicol) || find2(mat,x,midrow+1,hirow,locol,midcol) || find2(mat,x,midrow+1,hirow,midcol+1,hicol);
else
return find2(mat,x,lorow,midrow,locol,midcol) || find2(mat,x,lorow,midrow,midcol+1,hicol) ||find2(mat,x,midrow+1,hirow,locol,midcol);
}
source to share