Find element in sorted matrix

Question

Find an element in a MxN matrix where each row and column is sorted in ascending order.

Any comments on my code? (I added some test cases on non square matrices which I did not copy here)

import static org.junit.Assert.*;

import org.junit.Test;

public class Sol {

  public class Coord{
    int x;
    int y;

    public Coord(int _x, int _y){
      x = _x;
      y = _y;
    }
  }

  public Coord findElt(int[][] matrix, int elt, int begin_row, int end_row,
          int begin_col, int end_col){

    if (end_row < begin_row || end_col < begin_col){
      return new Coord(-1, -1);
    }

    if (begin_row == end_row && begin_col == end_col && matrix[begin_row][begin_col] != elt){
      return new Coord(-1, -1);
    }


    int mid_row = (begin_row + end_row)/2;
    int mid_col = (begin_col + end_col)/2;
    int current = matrix[mid_row][mid_col];


    if (current == elt){
    return new Coord(mid_row, mid_col);
  }

    else{
      Coord ur = findElt(matrix, elt, begin_row, mid_row, mid_col + 1, end_col);

      if (ur.x >= 0){
        return ur;
      }

      Coord bl = findElt(matrix, elt, mid_row + 1, end_row, begin_col, mid_col);

      if (bl.x >= 0){
        return bl;
      }

      if (elt > current){
        return findElt(matrix, elt, mid_row + 1, end_row, mid_col + 1, end_col);
      }
      else{
        return findElt(matrix, elt, begin_row, mid_row, begin_col, mid_col);
      }
    }

  }

  public Coord findElt(int[][] matrix, int elt){
    return findElt(matrix, elt, 0, matrix.length-1, 0, matrix[0].length-1);
  }

  @Test
  public void test_0(){
    int[][] mat = new int[3][3];

    mat[0][0] = 1;
    mat[0][1] = 2;
    mat[0][2] = 3;
    mat[1][0] = 2;
    mat[1][1] = 3;
    mat[1][2] = 5;
    mat[2][0] = 3;
    mat[2][1] = 4;
    mat[2][2] = 7;

    assertEquals(-1, findElt(mat, 8).x);
    assertEquals(-1, findElt(mat, 8).y);
  }

  @Test
  public void test_1(){
    int[][] mat = new int[3][3];

    mat[0][0] = 1;
    mat[0][1] = 2;
    mat[0][2] = 3;
    mat[1][0] = 2;
    mat[1][1] = 3;
    mat[1][2] = 5;
    mat[2][0] = 3;
    mat[2][1] = 4;
    mat[2][2] = 7;

    assertEquals(0, findElt(mat, 1).x);
    assertEquals(0, findElt(mat, 1).y);
  }

  @Test
  public void test_2(){
    int[][] mat = new int[3][3];

    mat[0][0] = 1;
    mat[0][1] = 2;
    mat[0][2] = 3;
    mat[1][0] = 2;
    mat[1][1] = 3;
    mat[1][2] = 5;
    mat[2][0] = 3;
    mat[2][1] = 4;
    mat[2][2] = 7;

    assertEquals(1, findElt(mat, 3).x);
    assertEquals(1, findElt(mat, 3).y);
  }

  @Test
  public void test_3(){
    int[][] mat = new int[3][3];

    mat[0][0] = 1;
    mat[0][1] = 2;
    mat[0][2] = 3;
    mat[1][0] = 2;
    mat[1][1] = 3;
    mat[1][2] = 5;
    mat[2][0] = 3;
    mat[2][1] = 4;
    mat[2][2] = 7;

    assertEquals(2, findElt(mat, 7).x);
    assertEquals(2, findElt(mat, 7).y);
  }


  public static void main(String[] args){
    int N = 3;
    int[][] mat = new int[N][N];
    Sol ex = new Sol();

    mat[0][0] = 1;
    mat[0][1] = 2;
    mat[0][2] = 3;
    mat[1][0] = 2;
    mat[1][1] = 3;
    mat[1][2] = 5;
    mat[2][0] = 3;
    mat[2][1] = 4;
    mat[2][2] = 7;

    ex.test_0();
    ex.test_1();
    ex.test_2();

    Coord a = ex.findElt(mat, 4);
    System.out.println(a.x + " " + a.y);

  }
}

Answer 1

Your Coord class should be a static nested class. There is no need for it to carry a reference to the parent Sol instance.

Additionally, you have mixed up two different coordinate systems. X and Y correspond to columns and rows respectively. It is always complicates when the systems are mixed together.

Since your algorithm is based on rows and columns, you should name the values in Coord as row and col (or similar).

Finally, your algorithm is awfully complicated. The entire thing can be simplified to:

public Coord findElt(int[][] matrix, int elt) {
    for (int r = 0; r < matrix.length; r++) {
        int pos = Arrays.binarySearch(matrix[r], elt);
        if (pos >= 0) {
            // found the value at the pos.
            return new Coord(pos, r);
        }
        if (pos == -1) {
            // all values in this row, and all later rows
            // are too large.
            break;
        }
    }
    return new Coord(-1,  -1);
}

This finds the value in the first row it could be in. This is slightly different to your algorithm which finds it in a diagonal. For example, when you search for 3 you find it here:

  1    2    3  
  2  [ 3]   5  
  3    4    7

but when I search for it, I find it here:

  1    2  [ 3] 
  2    3    5  
  3    4    7  

I have added some display code to yours, and coded it differently, like this:

public static final class Coord {
    private final int col;
    private final int row;

    public Coord(int _col, int _row) {
        col = _col;
        row = _row;
    }
}

private static final void displayMatrix(int[][] matrix, Coord coord) {
    StringBuilder sb = new StringBuilder(matrix.length * (matrix[0].length * 5) + matrix.length);
    for (int r = 0; r < matrix.length; r++) {
        for (int c = 0; c < matrix[r].length; c++) {
            if (r == coord.row && c == coord.col) {
                sb.append(String.format("[%2d] ", matrix[r][c]));
            } else {
                sb.append(String.format(" %2d  ", matrix[r][c]));
            }
        }
        sb.append("\n");
    }
    System.out.println(sb);
}

public static Coord findElt(int[][] matrix, int elt) {
    for (int r = 0; r < matrix.length; r++) {
        int pos = Arrays.binarySearch(matrix[r], elt);
        if (pos >= 0) {
            return new Coord(pos, r);
        }
        if (pos == -1) {
            // all values in this row, and all later rows
            // are too large.
            break;
        }
    }
    return new Coord(-1,  -1);
}

Note that all the methods are now static (there's no need for any instance data).

The Coord class is static, and the row/col fields are final.

I have put this all in to Ideone, and you can see the results there

Answer 2

When creating matrices, you can use the more concise syntax

int[][] m = {
  { 1, 2, 3 },
  { 2, 3, 5 },
  { 3, 4, 7 }
};