**Solution**

**Search a 2D Matrix II** https://leetcode.com/problems/search-a-2d-matrix-ii/

**Algorithm**

- At each iteration, eliminate either a row or a column.
- Complexity will be O(M+N).

```
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
M = len(matrix)
if M == 0:
return False
N = len(matrix[0])
if N == 0:
return False
rs, ce = 0, N-1
while rs < M and ce > -1:
if target == matrix[rs][ce]:
return True
elif target < matrix[rs][ce]:
ce = ce - 1
else:
rs = rs + 1
return False
```