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? — Bernhard Barker
– Bernhard Barker, Commented Jan 2, 2018 at 13:21

Sanket Makani · Accepted Answer · 2017-06-10 18:45:08Z

1

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);
}

edited Jun 10, 2017 at 18:45

answered Jun 10, 2017 at 14:44

Sanket Makani

2,4892 gold badges17 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Meni Over a year ago

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.

Sanket Makani Over a year ago

@Meni, Yup that condition is left to be checked . You can add it to terminate the recursion calls.

gati sahu · Accepted Answer · 2017-06-10 14:37:04Z

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, 2017 at 14:37

gati sahu

2,6512 gold badges12 silver badges16 bronze badges

4 Comments

Meni Over a year ago

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

gati sahu Over a year ago

I think it is O(n) and for mn matrix it will be O(m+n).can you please explain me how come to O (nn)

Meni Over a year ago

yes i am sorry its O(n) but the answer i am trying to achieve here is O(log(n))

Mr code. Over a year ago

@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

Collectives™ on Stack Overflow

Binary Search 2D array - Java

2 Answers 2

2 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related