# 74 Search a 2D Matrix

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:

`````` 1  (3)  5   7
10  11  16  20
23  30  34  60

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

Example 2:

`````` 1   3   5   7
10  11  16  20
23  30  34  60

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
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: def binary_search(lst, l, m): if l == m: return l, lst[l] == target mid = (l + m + 1) // 2 if lst[mid] == target: return mid, True if lst[mid] > target: return binary_search(lst, l, mid-1) return binary_search(lst, mid, m) heads = [r for r in matrix] row, _ = binary_search(heads, 0, len(heads)-1) _, res = binary_search(matrix[row], 0, len(matrix)-1) return res``````