题目

编写一个高效的算法来搜索 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，根据每行都是递增的这个原则，这一行的元素都会小于target，则抛弃这行元素。
• 若右上角的元素大于target，根据每列都是递增的这个原则，这一列的元素都会大于target，则抛弃这列元素。
  不断循环，直到找到目标值为止

func searchMatrix(matrix [][]int, target int) bool {
	m := len(matrix)
	n := len(matrix[0])
	i, j := 0, n-1           // 从右上角开始
	for i <= m-1 && j >= 0 { // 还有剩余元素
		if matrix[i][j] == target {
			return true
		}
		if matrix[i][j] < target {
			i++
		} else {
			j--
		}
	}
	return false
}