Search a 2D Matrix

1. Problem Description

Write an efficient algorithm to search for a target value target in an m x n matrix. The matrix has the following properties:

The elements in each row are sorted in ascending order from left to right. The elements in each column are sorted in ascending order from top to bottom.

2. Approach

1. Approach 1
   • Start from the top-right corner and search toward the bottom-left
2. Approach 2
   • Use binary search on each row

3. Implementation

func searchMatrix(matrix [][]int, target int) bool {
    row := 0
    col := len(matrix[0])-1
    for row < len(matrix) && col >= 0 {
        if matrix[row][col] < target {
            row++
        }else if matrix[row][col] > target {
            col--
        }else {
            return true
        }
    }
    return false
}

4. References

• 240. Search a 2D Matrix II - LeetCode