I think this question's optimal answer is on CTCI. The time complexity is O(N+M).

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(!matrix.empty()) {
int x = matrix[0].size() - 1, y = 0;
while(x >= 0 && y < matrix.size()) {
if(matrix[y][x] == target) {
return true;
} else if(matrix[y][x] > target) {
x--;
} else {
y++;
}
}
}
return false;
}
```