/**
1. 因为要高效的去找,所以要尽可能多的判掉不可能的值
2. 根据矩阵的两个特性, 我们对每个矩阵可以设定 start = matrix[0][m-1] 为基础进行查找
    2.1 每行的元素从左到右升序排列 -> target > start时target必定不在这一行 -> 缩小一行
    2.2 每列的元素从上到下升序排列 -> target < start时target必定不在这一行 -> 缩小一列
    2.3 每次可以把 matrix 缩小, 当target == start 即为所求, 如果遇到边界还没找到, 返回false
3. 复杂度为O(n + m)
*/

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

}