Cracking Coding Interview - 10.9 Sorted Matrix Search

1
2
3
4

1, 2, 3, 4
2, 3, 4, 5
3, 4, 5, 6
4, 5, 6, 7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

public RowCol {
  final int row;
  final int col;
  public RowCol(int row, int col) {
    this.row = row;
    this.col = col;
  }
  public boolean isGreaterThan(Row another) {
    return this.row > another.row && this.col > another.col;
  }
  public boolean isNotFound() {
    return row == -1 && col == -1;
  }
  public RowCol minusRow() {
    return new RowCol(row - 1, col);
  }
  public RowCol plusRow() {
    return new RowCol(row + 1, col);
  }
  public RowCol minusCol() {
    return new RowCol(row, col - 1);
  }
  public RowCol plusCol() {
    return new RowCol(row, col + 1);
  }
  public RowCol mid(RowCol another) {
    return new RowCol((row + another.row) / 2, (col + another.col) / 2);
  }
}

public RowCol search(int[][] matrix, int n) {
  int rows = matrix.length;
  int cols = matrix[0].length;
  return search(matrix, n, new RowCol(0, 0), new RowCol(rows - 1, cols - 1));
}

private RowCol search(int[][] matrix, int n, RowCol start, RowCol end) {
  if (start.isGreaterThat(end)) {
    return RowCol(-1, -1);
  }
  RowCol mid = start.mid(end);
  int midValue = matrix[mid.row][mid.col];
  if (n == midValue) {
    return mid;
  }
  if (n < midValue) {
    RowCol tmp = search(matrix, n, start, mid.minusRow());
    if (tmp.isNotFound()) {
      return search(matrix, n, start, mid.minusCol());
    }
    return tmp;
  }
  RowCol tmp = search(matrix, n, mid.plusRow(), end);
  if (tmp.isNotFound()) {
    return search(matrix, n, mid.plusCol(), end);
  }
  return tmp;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public int[] search(int[][] matrix, int n) {
  int row = 0;
  int col = matrix[0].length - 1;
  while (row <= matrix.length - 1 && col >= 0) {
    if (matrix[row][col] == n) {
      return new int[row, col];
    } else if (matrix[row][col] > n) {
      col--;
    } else {
      row++;
    }
  }
  return new int[] {-1, -1};
}