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