二维数组中的查找

题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例
输入数组：
[
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
]
如果输入查找数值为7，则返回true，
如果输入查找数值为5，则返回false。

解法一：二分

笨笨的我只想到了一行一行二分，没用上每一列从上到下递增的性质
时间复杂度O(nlogn)，空间复杂度O(1)

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        for (int i = 0; i < array.size(); i++) {
            int l = 0, r = array[i].size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (array[i][mid] <= target)
                    l = mid;
                else r = mid - 1;
            }
            if (array[i][l] == target)
                return true;
        }
        return false;
    }
};

解法二：从右上角或左下角出发

右上角是第一行的最大值，最后一列的最小值，因此可以有所作为，左下角类似
只想着从左上角开始，从行和列的角度来看都是最小值，迷茫
时间复杂度O(n+m)，n为行，m为列；空间复杂度O(1)

class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
        if (array.empty()) return false;
        int l = 0, r = array[0].size() - 1;
        while (l < array.size() && r >= 0) {
            if (array[l][r] == target)
                return true;
            else if (array[l][r] < target) {
                l++;
            }
            else {
                r--;
            }
        }
        return false;
    }
};