Search a 2D Matrix II-LeetCode#240

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:
Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.
矩阵搜索
编写一个有效的算法，搜索m×n矩阵中的值。此矩阵具有以下属性：

1. 每行中的整数按从左到右的升序排序。
2. 每列中的整数按从上到下的顺序排序。

思路：矩阵中搜索一个数，最普通的循环遍历出每个数与target比较。

public boolean searchMatrix(int[][] matrix, int target) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

但是本题很有意思的是，矩阵是经过排序的。左至右升序，上至下升序。
另一个思路是从右上角的数开始查询，与target比较判断，向左或者向下走

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length <= 0 || matrix[0].length <= 0) return false;
    if (target < matrix[0][0] || target > matrix[matrix.length - 1][matrix[0].length - 1]) return false;
    int i = 0;
    int j = matrix[0].length - 1;
    while (true) {
        if (matrix[i][j] > target) {
            --j;
        }else if (matrix[i][j] < target){
            ++i;
        }else {
            return true;
        }
        if (j < 0 || i >= matrix.length) break;
    }
    return false;
}