算法一：两次二分$O(logn + logn)$

1. 找到第一行比target小的最大元素，因为矩阵从上到下都是递增的，所以目标值一定在找到的这个元素的这一列
2. 二分找到元素的这一列

class Solution {
    public boolean searchArray(int[][] array, int target) {
        if (array.length == 0 || array[0].length == 0) return false;
        int l = 0, r = array[0].length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (array[0][mid] <= target) l = mid;
            else r = mid - 1;
        }
        int col = l;
        l = 0;
        r = array.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (array[mid][col] >= target) r = mid;
            else l = mid + 1;
        }
        return array[l][col] == target;
    }
}

算法二：单调线性扫描$O(n + m)$

发现矩阵右上方元素$x$的性质：

1. $x$同一行左侧的元素都比$x$小
2. $x$同一列下方所有元素都比$x$大

排除一整行就是让枚举的点的横坐标加一，排除一整列就是让纵坐标减一。 当我们排除完整个矩阵后仍没有找到目标值时，就说明目标值不存在，返回false。

class Solution {
    public boolean searchArray(int[][] array, int target) {
        if (array.length == 0 || array[0].length == 0) return false;
        int i = 0, j = array[0].length - 1;
        while (i < array.length && j >= 0) {
            if (array[i][j] == target) return true;
            else if (array[i][j] < target) i ++;
            else j --;
        }
        return false;
    }
}