# Search a 2D Matrix

Sources: leetcode 74

Rating: medium

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.
```def searchMatrix(matrix: List[List[int]], target: int) -> bool:
# return if the target appears in matrix
```

Solution

The fact that the matrix is sorted in order immediately gives away that the intended algorithm is a binary search, just applied twice in both dimensions.

```def searchMatrix(matrix, target):
if len(matrix) == 0:
return False
# binary search through rows
# binary search through columns
```

First, go through the rows from top t to bottom b in a binary search to locate the row where the target would be if it is in the matrix.

```def searchMatrix(matrix, target):
if len(matrix) == 0:
return False
t, b = 0, len(matrix) - 1
while t < b:
m = (t + b) // 2 + 1
if matrix[m] == target:
return True
elif matrix[m] < target:
t = m
else:
b = m - 1
# binary search through columns
```

Next, use a binary search to locate the column between left l and right r.

```def searchMatrix(matrix, target):
if len(matrix) == 0:
return False
t, b = 0, len(matrix) - 1
while t < b:
m = (t + b) // 2 + 1
if matrix[m] == target:
return True
elif matrix[m] < target:
t = m
else:
b = m - 1
l, r = 0, len(matrix) - 1
while l <= r:
m = (l + r) // 2
if matrix[t][m] == target:
return True
elif matrix[t][m] < target:
l = m + 1
else:
r = m - 1
```

If the binary search completes without finding the target, return false.

Final Code

```def searchMatrix(matrix, target):
if len(matrix) == 0:
return False
t, b = 0, len(matrix) - 1
while t < b:
m = (t + b) // 2 + 1
if matrix[m] == target:
return True
elif matrix[m] < target:
t = m
else:
b = m - 1
l, r = 0, len(matrix) - 1
while l <= r:
m = (l + r) // 2
if matrix[t][m] == target:
return True
elif matrix[t][m] < target:
l = m + 1
else:
r = m - 1
return False
```