题目描述#

给定一个 m x n 的整数矩阵 matrix，它满足两个条件：

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

现在要判断 target 是否存在于矩阵中。如果存在，返回 true；否则返回 false。嘿嘿，这个矩阵看起来是二维的，其实从整体顺序看，就像一条被折成好多行的有序长队伍嘛～

二维矩阵别慌，先盯行，再盯列，咱一层层拍清楚～

思路#

这题可以把矩阵看成一个整体有序的数组，也可以像代码里这样分两步做二分。第一步先确定 target 可能在哪一行：对每一行的第一个元素做二分，找到最后一个满足 matrix[row][0] <= target 的行。

为什么是最后一个行首不大于 target 的行呢？因为每一行的第一个数都大于上一行的最后一个数，所以如果某一行的行首已经大于 target，那它以及后面的行都不可能包含 target。循环结束后，right 就是最后一个行首 <= target 的行下标。

如果 right < 0，说明 target 比第一行第一个数还小，直接返回 false。否则就在 row := right 这一行里继续做普通二分，查找 target 是否存在。没错没错，先找楼层，再找房间号，思路一下就顺了嘛～

整个过程用了两次二分：一次在行首数组上找行，一次在目标行里找列，时间复杂度是 O(log m + log n)。照片当然不是现实，但把行和列分开拍，混乱的二维世界也会变得清清楚楚啦。好啦，三、二、一，咔嚓！

思维边界#

• 矩阵非空：代码直接读取 matrix[0]，因此依赖题目给出的有效矩阵输入。
• 行定位含义：第一轮二分结束后，right 是最后一个满足 matrix[right][0] <= target 的行下标。
• row < 0：说明 target 小于矩阵第一个元素，不可能存在。
• 行内二分：确定候选行之后，第二轮就是普通的一维有序数组查找。
• 复杂度：两次二分分别处理行数和列数，总时间复杂度为 O(log m + log n)，空间复杂度为 O(1)。

本姑娘小结：先用行首锁定行，再在这一行里二分，搞定搞定～

代码#

func searchMatrix(matrix [][]int, target int) bool {
	m := len(matrix)
	n := len(matrix[0])
	if m == 1 && n == 1 {
		return target == matrix[0][0]
	}
	left, right := 0, m-1
	for left <= right {
		mid := left + (right-left)/2
		if matrix[mid][0] == target {
			return true
		} else if matrix[mid][0] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	// right 是 最后一个 <= target 的
	row := right
	if row < 0 {
		return false
	}
	left, right = 0, n-1
	for left <= right {
		mid := left + (right-left)/2
		if matrix[row][mid] == target {
			return true
		} else if matrix[row][mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return false
}