方法一：二分法+双指针

思路：观察可知，左下角的数组值是其所在行最小值且为所在列最大值，于是有：
(1) 如果 左下角元素大于目标值，则目标值一定位于该行的上方， 左下角元素所在行可以消除。
(2) 如果 左下角元素小于目标值，则目标值一定位于该列的右方， 左下角元素所在列可以消除。
注：其实从左下角和右上角开始走，都是相同的思路。

class Solution {
   
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
   
        // 特例
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    // 当数组不存在，或为空时，直接返回false。
            return false;
        }
        // 二分查找
        int n = matrix.length, m = matrix[0].length; // 行标和列表
        int i = n - 1, j = 0; // 从左下角开始遍历
        while (i >= 0 && j < m) {
   
            if (matrix[i][j] > target) {
    // 当前值大于目标值，则说明当前值所在行都大于目标值，因此，需要消除该行。
                i -= 1;
            }else if (matrix[i][j] < target) {
    // 当前值小于目标值，则说明当前值所在列都小于目标值，因此，需要消除该列。
                j += 1;
            }else{
    // 查找到目标值，返回true。
                return true;
            }
        }
        return false; // 未找到目标值，返回false。
    }
}

时间复杂度：O(M + N), N和M分别为数组行数和列数，该算法最多循环M + N 次。
空间复杂度：O(1), 未使用额外空间。