240. Search a 2D Matrix II

左下到右上二分 O(m+n) time O(1) space
这道题跟74. Search a 2D Matrix的区别是从左上到右下并非严格递增，所以不能直接用全矩阵二分（复杂度更低）不过这个方法是可以用到那道题上的

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int r = m - 1, c = 0;
        while (r >= 0 && c < n) {
            if (matrix[r][c] == target) return true;
            if (matrix[r][c] > target) {
                --r;
            } else {
                ++c;
            }
        }
        return false;
    }
};