240. 搜索二维矩阵 II

[yankewei]

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。
给定 target = 20，返回 false。

解答

暴力法

遍历即可

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
        return false
    }
    row, column := len(matrix), len(matrix[0])
    for i :=0; i < row; i++ {
        for j := 0; j < column; j++ {
            if matrix[i][j] == target {
                return true
            }
        }
    }
    return false
}

从每行的尾部向前遍历

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

二分查找

二分查找看似简单，但是溢出和边界都有坑

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
	return false
    }
    row, column := len(matrix), len(matrix[0])
    for i := 0; i < row; i++ {
	l, r := 0, column-1
        for l <= r {
            mid := (l + r) / 2
            if matrix[i][mid] == target {
	        return true
	    }
	    if matrix[i][mid] > target {
		r = mid - 1
	    } else {
		l = mid + 1
	    }
        }
    }
    return false
}