class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if (!matrix.size() || matrix.size() == 1 && !matrix[0].size()) {
                return false;
        }
        for (int i = 0; i < matrix.size(); ++i){
            if (matrix[i][0] > target) {
                return false;
            }
            if (matrix[i].back() < target) {
                continue;
            }
            for (int j = 0; j < matrix[i].size(); ++j) {
                if (matrix[i][j] == target) {
                    return true;
                }
                if (matrix[i][j] > target) {
                    break;
                }
            }
        }
            return false;
    }
};