# Leetcode 74 - Search a 2D Matrix ### Understanding the problem

The problem statement on LeetCode reads as follows:

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.

Example 1:

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

Example 2:

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

One way to solve this problem is to use a binary search algorithm. Since the rows of the matrix are sorted in increasing order, we can use binary search to find the row that the target value is in. Once we find the row, we can use binary search again to find the target value within that row.

Now that we have a plan, let’s implement it in Python.

``````def searchMatrix(matrix, target):
# Edge case: if the matrix is empty, return False
if not matrix:
return False

# Find the row that the target value is in using binary search
left = 0
right = len(matrix) - 1
while left <= right:
mid = (left + right) // 2
if matrix[mid] <= target <= matrix[mid][-1]:
row = mid
break
elif matrix[mid] > target:
right = mid - 1
else:
left = mid + 1
else:
return False

# Find the target value within the row using binary search
left = 0
right = len(matrix[row]) - 1
while left <= right:
mid = (left + right) // 2
if matrix[row][mid] == target:
return True
elif matrix[row][mid] > target:
right = mid - 1
else:
left = mid + 1

return False
``````