Search a 2D Matrix
给你一个由整数 matrix 组成的网格，它有 m 行和 n 列，还有一个整数 target。每一行都按升序排列，并且每一行的第一个值都大于上一行的最后一个值。如果网格中出现了 target，则返回 true，否则返回 false，时间复杂度为 O(log(m × n))。
函数
- matrixinteger-2d-array
- 网格以行列表的形式给出，并按行排序
- targetinteger
- 要查找的值
- 返回值boolean
- 如果目标位于网格中，则为 true，否则为 false
约束条件
1 ≤ m, n ≤ 100，其中m = matrix.length，n = matrix[i].length- 每一行的长度都相同，为
n。 -104 ≤ matrix[i][j], target ≤ 104- 每一行都按严格递增的顺序排列，并且每一行的第一个值都大于上一行的最后一个值。
示例
- 输入
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 26
- 输出
- true
- 解释
- 按行读取，这 12 个值构成一个有序列表。对位置 0 到 11 进行二分查找：先检查位置 5 的 21（太小），再检查位置 8 的 33（太大），然后在位置 6 找到 26。
- 输入
- matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]]target = 16
- 输出
- false
- 解释
- 16 会排在第 0 行的最后一个值 14 之后、第 1 行的第一个值 17 之前。它们之间没有任何值，所以 16 不在网格中。
进阶
假设这些行的长度可能不同，但所有元素从头到尾仍然有序。你会如何把一个位置转换成行和列？搜索的开销是多少？
提示
逐个打开提示，每个都会多透露一点。
按行读取这个矩阵，从左到右，就像它是一个很长的列表一样。你注意到列表中的值有什么顺序特点？
这两条规则合在一起，意味着整个矩阵按行读取时就是一个由
m × n个值组成的有序列表。你无需实际构建这个列表，就能对它进行二分查找。在位置
0到m × n - 1之间进行二分查找。位置p位于第p / n行、第p % n列（整数除法），因此每一步都会读取一个单元格，并舍弃剩余位置的一半。
题解
两条排序规则结合起来后，按行读取网格，就会得到一个由 m × n 个值组成的有序列表。按位置对这个列表进行二分查找，再用一次除法把每个位置转换回行和列。一个 100 × 100 的网格最多只需 14 次比较，而不是 10000 次。
检查每个单元格
思路
将每个单元格与 target 比较，匹配时返回 true，检查完最后一个单元格后返回 false。它会读取每个单元格，因此适用于任何网格，无论网格是否经过排序。它完全不利用顺序，因此对于 100 乘 100 的网格，最多需要进行 10000 次比较。
算法
- 对于
matrix的每一行，按顺序查看其中的每个值。 - 如果该值等于
target，则返回true。 - 循环结束后，返回
false。
def searchMatrix(matrix, target):
for row in matrix:
for value in row:
if value == target:
return True
return False从右上角走
思路
从右上角的单元格开始，左边的值都更小，下方的值都更大。如果单元格中的值大于 target，它下方的整列也都更大：向左移动，并排除这一列。如果它更小，它左边的整行也都更小：向下移动，并排除这一行。
在第一个示例中，14 小于 26，所以向下移动到 30。30 更大，所以向左移动到 26，找到匹配值。每一步都会排除一行或一列，因此最多需要 m + n 步：对于一个 100 乘 100 的网格，需要 200 步。这种查找方法只要求行和列分别有序，因此它没有利用这个网格提供的一半信息。
算法
- 从第
0行和最后一列开始。 - 当行和列都在网格内时，读取单元格。
- 如果它等于
target，返回true。 - 如果它更大，就向左移动一列；如果它更小，就向下移动一行。
- 离开网格时，返回
false。
def searchMatrix(matrix, target):
# Start at the top-right corner: left is smaller, down is larger.
r, c = 0, len(matrix[0]) - 1
while r < len(matrix) and c >= 0:
value = matrix[r][c]
if value == target:
return True
if value > target:
c -= 1 # every value below in this column is larger still
else:
r += 1 # every value to the left in this row is smaller still
return False在展平后的网格中进行二分查找
思路
按行给单元格编号：第 0 行包含位置 0 到 n - 1，第 1 行包含从 n 到 2n - 1 的位置，依此类推。每一行都已排序，并且起始位置在上一行结束位置之后，所以值会随位置递增。这就是一个有序列表，可以使用二分查找。
你不需要构建这个列表。位置 p 位于第 p / n 行和第 p % n 列，其中使用整数除法。在第一个示例中，n = 4，所以位置 6 位于第 1 行、第 2 列，对应的值是 26。每次比较都会将可能存放 target 的位置减半：对于 10000 个单元格，最多需要 14 次比较，只需额外使用两个索引的内存。
算法
- 令
m和n分别表示行数和列数，并设置lo = 0、hi = m × n - 1。 - 当
lo ≤ hi时，取它们中间的mid。 - 读取
value = matrix[mid / n][mid % n]。 - 如果
value等于target，则返回true。如果它更小，则设置lo = mid + 1；否则设置hi = mid - 1。 - 循环结束后，返回
false。
def searchMatrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
# Read row by row, the cells form one sorted list of rows * cols values.
# Position p of that list is matrix[p // cols][p % cols].
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = (lo + hi) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
lo = mid + 1
else:
hi = mid - 1
return False
易错点和边界情况
- 用行数而不是列数进行除法。位置
p所在的行是p / n；把n换成m后，代码在正方形网格上可以通过，但在 3 行 4 列的网格上会失败。 - 在使用两次搜索的版本中，没有处理
target小于matrix[0][0]的情况。没有任何一行的起始值小于或等于它，而且行索引-1会进入第二次搜索。 - 使用包含
hi的区间，却用lo < hi作为循环条件。对于存放着target的 1 × 1 网格，结果会是false，因为循环不会运行。 - 在 Lua 和 R 中，忘记将索引调整为从 1 开始：位置
p所在的行是p / n + 1，列是p % n + 1。
常见问题3
搜索二维矩阵的时间复杂度是多少？
在展平后的网格上进行二分查找，时间复杂度为 O(log(m × n))，空间复杂度为 O(1)：对于 10000 个单元格，最多需要比较 14 次。由于 log(m × n) = log m + log n，它与先查找行、再在该行中查找的复杂度相同。
你应该使用右上角行走法还是二分查找？
沿角落移动需要 O(m + n) 步，只要求行和列分别有序，因此也能解决每一行的起始位置可能低于上一行末尾的变体。像这里这样，每一行的起始位置都高于上一行的末尾时，二分查找更快。
进行两次二分查找，一次查找行，另一次在行内查找，这样也正确吗？
是的。先在第一列中使用二分查找，找到第一个值不大于 target 的最后一行，然后在该行中进行二分查找。它的运行时间为 O(log m + log n)，渐进复杂度相同。单次搜索用一个循环就能完成相同的工作，而且边界情况更少。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def searchMatrix(matrix, target):
# 在这里编写代码测试 #1
测试 #2
参数
matrix = [[2, 5, 9, 14], [17, 21, 26, 30], [33, 38, 45, 52]] target = 26
预期输出
true