# 74. Search a 2D Matrix

## 30 Dec 74. Search a 2D Matrix

Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix `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.

Example 1:

```Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
```

Example 2:

```Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
```

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 100`
• `-104 <= matrix[i][j], target <= 104`

class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0:
return False

m = len(matrix)
n = len(matrix)
row = 0
column = n-1
while row < m and column >=0:
if matrix[row][column] == target:
return True
elif matrix[row][column] > target:
column = column -1
elif matrix[row][column] < target:
row = row + 1
return False
• Intuition, since the rows are sorted, columns are sorted as well, thus we can do 2 binary search to locate the exact position of `target`
• First, handle special cases. e.g. `[], [[]]`
• Second, binary search on rows, to locate row number
• If not found, return `False`
• Third, once we have row number, binary search on columns
• If not found, return `False`, else return `True`
• Time Complexity `O(lgm + lgn) == O(lg(mn))`
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0:
return False

m = len(matrix)
n = len(matrix)
current_row = -1
first_row = 0
last_row = m -1
while first_row <= last_row:
middle_row = (first_row + last_row) // 2
print(middle_row)
if matrix[middle_row] <= target <= matrix[middle_row][n-1]:
current_row = middle_row
break
elif matrix[middle_row][n-1] < target:
first_row = middle_row + 1
else:
last_row = middle_row – 1
print(“row————————————“)
print(current_row)
print(“current row————————————“)

first_column = 0
last_column= n-1

while first_column <= last_column:
middle_column=(first_column + last_column) // 2
print(middle_column)
print(matrix[current_row][middle_column])
if matrix[current_row][middle_column] == target:
return True
elif matrix[current_row][middle_column] < target:
first_column = middle_column + 1
elif matrix[current_row][middle_column] > target:
last_column = middle_column – 1
print(“column————————-“)
return False