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][0] == target:
return True
elif matrix[m][0] < 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][0] == target:
return True
elif matrix[m][0] < target:
t = m
else:
b = m - 1
l, r = 0, len(matrix[0]) - 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
# handle case for if target not found after search completes

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][0] == target:
return True
elif matrix[m][0] < target:
t = m
else:
b = m - 1
l, r = 0, len(matrix[0]) - 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

### Like this:

Like Loading...

*Related*