74. 搜索二维矩阵

74. 搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。

• 每行的第一个整数大于前一行的最后一个整数。

  
  示例 1：
  
  输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
  输出：true

//转换为一维的数组，全部遍历一遍二分，    
//时间Ologm*n,空间O1
func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    l, r := 0, m*n
    for l < r {
        mid := (l + r) / 2
        if matrix[mid/n][mid%n] < target {
            l = mid + 1
        } else if matrix[mid/n][mid%n] > target {
            r = mid
        } else {
            return true
        }
    }
    return false
}

//从右上角遍历，局部剪枝，复杂度O(m+n),空间O1
func searchMatrix(matrix [][]int, target int) bool {
    row := len(matrix)-1            //横的减少
    col:= 0                            //纵的增加

    for row >= 0 && col < len(matrix[0]){
        if matrix[row][col] == target{
            return true
        } else if matrix[row][col] > target{
            row--
        } else if matrix[row][col] < target{            //二分法要注意写else
            col++
        }
    }
    return false
}