74. Search a 2D Matrix
Medium
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
Runtime: 4 ms, faster than 72.55%
Memory Usage: 2.6 MB, less than 100%
func searchMatrix(matrix [][]int, target int) bool {
for _, row := range matrix {
if target > row[len(row) - 1] {
continue
} else{
return binarySearch(row, target)
}
}
return false
}
func binarySearch(row []int, target int) bool {
left, right := 0, len(row) - 1
for left <= right {
mid := (left + right) / 2
if row[mid] == target {
return true
} else if row[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return false
}
Last modified 6mo ago