leetcode74搜索二维矩阵

题目

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例

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

解析

这道题其实还是使用二分法，就相当于将所有的二维数组串起来（但并不是真的要有串起来实现的代码），比如上面的例子，target=3，有3行4列，m=3, n=4，则有：
x := matrix[mid/n][mid%n]
代码如下（左闭右开法）：

func searchMatrix(matrix [][]int, target int) bool {
   m := len(matrix)
   n := len(matrix[0])
   left := 0
   right := m * n
   for left < right {
   	mid := left + (right-left)/2
   	x := matrix[mid/n][mid%n]
   	if x == target {
   		return true
   	} else if x < target {
   		left = mid + 1
   	} else {
   		right = mid
   	}
   }
   return false
}

如果上面的方法不好记的话，可以记『搜索二维矩阵II』同样的代码：

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

	return false
}