Binary Search 2D array - Java

Question

I am stuck on the following question:

Given a int two-dimensional matrix mat of size n² where n = 2^k, search for an integer k.

The matrix's rows and columns are sorted.

If we split the matrix in quarters, each quarter is also sorted. For example, given this matrix:

-4 -2 5  9
 2  5 12 13
13 20 25 25
22 24 49 57

If we split it into quarters, we can see that all of the numbers in the first quarter are equal or less than numbers in the second quarter.

In order to obtain an efficient algorithm, I thought of making a recursive binary search in on the two dimensions but it fails to search for 2 on 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.

Related question (without the sorted-by-quadrant constraint): [How do I search for a number in a 2d array sorted left to right and top to bottom?](https://stackoverflow.com/q/2457792) — Bernhard Barker, Jan 02 '18 at 13:21

Sanket Makani · Answer 1 · 2017-06-10T18:45:08.990

Your mistake is at 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 first two functions, You are removing middle column from your search space. You need to include it as element can be present at the middle column. Another mistake is in the last call find2(mat,x,midrow+1,hirow,midcol+1,hicol).

If your search element is smaller than the middle element, You should choose top-left quadrant of the middle element and ignore the bottom-right quadrant. You have mistakenly considered here bottom-right quadrant over top-left quadrant.

After making changes accordingly the return function in else looks like:

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 solved the problem and it 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);
}

many thanks pal, but there is a bug in your code. for example if you insert input such as 0 or a number which is smaller than the first number in the matrix like -6 you get stack overflow error. — Meni, Jun 10 '17 at 18:16
@Meni, Yup that condition is left to be checked . You can add it to terminate the recursion calls. — Sanket Makani, Jun 10 '17 at 18:35

score 0 · Answer 2 · answered Jun 10 '17 at 14:37

0

If your matrix row and column are sorted 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;
    }

answered Jun 10 '17 at 14:37

gati sahu

2,576
2
10
16

thanks for your comment, yet your answer in not relevant for my question. your code's complexity is in order of O(n^2) which is not good – Meni Jun 10 '17 at 18:02
I think it is O(n) and for m*n matrix it will be O(m+n).can you please explain me how come to O (n*n) – gati sahu Jun 10 '17 at 18:15
yes i am sorry its O(n) but the answer i am trying to achieve here is O(log(n)) – Meni Jun 10 '17 at 18:31
@gati sahu your code has bug int[][] data = { {10,20,30,40}, {15,25,35,45}, {27,29,37,48}, {32,33,39,50} }; it will fail to find out 33 which is present at 2,3 – Mr code. Jun 17 '19 at 05:06

Binary Search 2D array - Java

2 Answers2