240.搜索二维矩阵II
240.搜索二维矩阵II
题解
题目:给一个从左到右递增,从上到下递增的二维矩阵,搜索一个数在不在矩阵中
思路:
一想就是二分
从左到右递增,从上到下递增的性质 其实可以从右上开始搜索 如果当前的数小于target,则进入下一行 如果当前的数大于target,则进入上一列
代码
func searchMatrix(matrix [][]int, target int) bool { for i, v := range matrix { idx := sort.SearchInts(v, target) if idx < len(v) && matrix[i][idx] == target { return true } } return false }
func searchMatrix(matrix [][]int, target int) bool { n, m := len(matrix), len(matrix[0]) x, y := 0, m-1 for x < n && y >= 0 { v := matrix[x][y] if v == target { return true } else if v > target { y-- } else { x++ } } return false }