240. Search a 2D Matrix II

本题不算难理解，但是解法很炫，第一次碰到，难免做不出来，而且由于带有Binary Search的Tag，会让人不由自主的往Binary Search想。
其实，可以把本题想做一个Tree，右上角为顶点

• target < matrix[i][j]: 向下移动
• target == matrix[i][j]: 找到了
• target > matrix[i][j]: 向左移动

示意图如上所示

• 时间复杂度：
• 空间复杂度：

代码如下：

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
      return false;
    }
    int row = 0;
    int col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
      int val = matrix[row][col];
      if (target == val) {
        return true;
      }
      else if (target > val) {
        ++row;
      }
      else {
        --col;
      }
    }
    return false;
  }
}

Tree