Given a 2D matrix that contains integers only, which each row is sorted in an ascending order. The first element of next row is larger than (or equal to) the last element of previous row.

Given a target number, returning the position that the target locates within the matrix. If the target number does not exist in the matrix, return {-1, -1}.

Assumptions:

• The given matrix is not null, and has size of N * M, where N >= 0 and M >= 0.

Examples:

matrix = { {1, 2, 3}, {4, 5, 7}, {8, 9, 10} }

target = 7, return {1, 2}

target = 6, return {-1, -1} to represent the target number does not exist in the matrix.

Solution: 因为行与列之间都是递增，所以可以从左下角出发，大于target时i--，小于target时j++，直到出界

  public int[] search(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
      return new int[] {-1, -1};
    }
    int i = matrix.length - 1, j = 0;
    while (i >= 0 && j < matrix[0].length) {
      if (matrix[i][j] == target) {
        return new int[] {i, j};
      } else if (matrix[i][j] > target) {
        i--;
      } else {
        j++;
      }
    }
    return new int[] {-1, -1};
  }