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
}