Learning GoLang Programming: Search in a 2D Sorted Matrix

justyy (81)in #programming • 3 years ago

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.

Search a 2D sorted Matrix via GoLang

Since the rows and cols are already sorted, we can start from the top-right or lower-left corner, and move accordingly by comparing the numbers. The time complexity is O(N+M) where N and M are the number of rows or columns in the matrix resepctively.

Start search from the top-right corner:

func searchMatrix(matrix [][]int, target int) bool {
    var rows, cols = len(matrix), len(matrix[0])
    var r, c = 0, cols - 1
    for r < rows && c >= 0 {
        if matrix[r][c] == target {
            return true
        }
        if target > matrix[r][c] {
            r ++
        } else {
            c --
        }
    }
    return false
}

And start from the lower-left corner:

func searchMatrix(matrix [][]int, target int) bool {
    var rows, cols = len(matrix), len(matrix[0])
    var r, c = rows - 1, 0
    for r >= 0 && c < cols {
        if matrix[r][c] == target {
            return true
        }
        if target > matrix[r][c] {
            c ++
        } else {
            r --
        }
    }
    return false
}

We can also binary search each rows in O(NLogM) time.

See other searching the element in the sorted 2D matrix:

Reposted from Blog