GoLang: 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.

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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
}

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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
}

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:

• How to Search in 2D Sorted Matrix?
• https://helloacm.com/teaching-kids-programming-search-in-a-2d-sorted-matrix/
• GoLang: Search a 2D Matrix

–EOF (The Ultimate Computing & Technology Blog) —