搜索二维矩阵 II（LeetCode 240，Medium）是「结构化查找」的优雅范本：矩阵每行从左到右升序、每列从上到下升序（注意：与 LeetCode 74「每行独立有序且行首大于上行行尾」的完全有序不同——240 只保证行、列各自有序，行与行之间没有全局序），在其中查找一个数。朴素 O(m×n) 全扫可以过，二分每行是 O(m log n)——而真正的答案是 O(m+n) 的 Z 字查找：从右上角出发，每一步比较都确定性地排除一行或一列。本篇讲清这条路径的玄机。
右上角起点：每一步排除一行或一列
为什么从右上角出发：站在右上角的元素上，它与目标的关系只有两种，而每种都确定性地排除一整块——当前元素大于目标：这一列从上到下都递增，右上角已是本列最小，本列全部大于目标，整列排除，左移一列；当前元素小于目标：这一行从左到右递增，右上角已是本行最大，本行全部小于目标，整行排除，下移一行；当前元素等于目标：找到。每一步的移动（左移或下移）都严格排除一行或一列，最多走 m+n-1 步（行数+列数-1）就能给出确定答案。代码极短：
def search_matrix(matrix: list[list[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
row, col = 0, len(matrix[0]) - 1 # 右上角
while row < len(matrix) and col >= 0:
cur = matrix[row][col]
if cur == target:
return True
if cur > target:
col -= 1 # 本列全部偏大，左移
else:
row += 1 # 本行全部偏小，下移
return False
起点可以换吗？可以——左下角同理（大于则上移、小于则右移）。但其他起点不行：从左上角出发，大于目标时无法排除（右边和下面都可能藏着目标）；从右下角同理——只有两个「极角」具备「每步确定排除」的性质，因为只有极角的两个方向是「单调反向」的。这个「极角唯一性」是本题最值得理解的结构性质。
对比：为什么不用二分——以及什么时候用
逐行二分的对比：对每行二分，O(m log n)——当 m 很小、n 很大时（3×10000），m log n < m+n，二分反而更快。而 Z 字查找是 O(m+n)——当行数列数相当时（500×500），Z 字完胜（1000 步 vs 500×9=4500 步）。结论：两者各有所长，选择看矩阵形状与分布——Z 字利用的是「行+列的双重序」的联合信息（每步排除行列的组合），逐行二分只利用行内序。什么时候用分治（对角线二分，O(n log n) 级别的进阶解法）？矩阵极大且需要反复查询时——但那已经超出本题的工程需要。本题的查找设计哲学值得提炼：好的查找不是「更快地比较」，是「每次比较排除尽可能多的候选」——二分每次排除一半，Z 字每次排除一行或一列，哈希每次排除几乎全部——排除率决定查找的效率。这个「排除率」视角统一了二分、Z 字、哈希、剪枝（本库《N 皇后》）所有查找与搜索的设计。
「每步排除」的通用心法与姊妹题
「每步排除一块」的心法可以迁移到一族问题。姊妹题一：LeetCode 378 有序矩阵中第 K 小的元素（同样的行列有序结构，查找第 K 小——用「值域二分 + 每步计数」的变体：二分答案值，统计矩阵中小于它的元素个数——每步排除的是值域的一半）。姊妹题二： Peaks 山峰查找类（一维数组找峰顶——每步比较 mid 与 mid+1，排除一半——一维版的「结构性排除」）。姊妹题三：旋转数组的搜索（本库《搜索旋转排序数组》——每次二分确定「哪一半是有序的」，排除无目标的一半）。共同心法：在有序或部分有序的结构上，找到一个「可以安全排除一块」的判定条件——找到它，查找就从遍历变成了导航。反面的教训也值得记录：结构不存在时强行套用（无序数组二分、无结构矩阵 Z 字）必然出错——「排除法」的前提永远是「结构保证排除的确定性」。
378 的值域二分详解：有序矩阵第 K 小的完整思路
本篇正文的姊妹题「有序矩阵中第 K 小的元素」（LeetCode 378）值得展开——它演示了「值域二分」的完整套路。问题：行列各自升序的 n×n 矩阵，找第 k 小的元素（不要求去重）。值域二分的框架：二分的对象不是「位置」而是「值」——对候选值 x，问「矩阵中 ≤ x 的元素有几个」（count(x)）；count 是 x 的单调不减函数——二分「最小的 x 使得 count(x) ≥ k」，那个 x 必然是矩阵中的元素（若 x 不在矩阵中，count(x)=count(x-1)，二分会继续下探）。count(x) 的计算：利用「行列各自升序」的结构——从左下角出发走「楼梯」（本篇正文的 Z 字查找同款起点）：每列从下往上找第一个 ≤ x 的位置——一趟 O(n)。总复杂度 O(n × log(值域范围))。值域二分 vs 位置查找的对比：本篇正文的 Z 字查找找的是「某个特定目标的位置」，378 的值域二分找的是「排名第 k 的值」——两者的搜索空间不同（位置空间 vs 值域空间），但「每步排除一块」的心法完全一致——Z 字排除行列，值域二分排除值的区间。这个框架的迁移性：一切「第 k 小/大」且「候选值域可二分 + 可快速计数」的问题，都适用值域二分——它是「排序太贵、堆太慢」时的第三选择。
Z 字查找的变体：从左下角与「对称实现」的等价性
Z 字查找的起点可以从右上角换成左下角——对称实现完全等价，但移动方向要镜像。左下角的规则：当前元素大于目标——这一列从下到上递增，左下角已是本列最大，整列排除，上移；当前元素小于目标——这一行从左到右递增，左下角已是本行最小，整行排除，右移。移动的镜像（上移+右移 vs 左移+下移）映射的是同一种「极角排除」逻辑。为什么两个极角等价、另外两个不行（本篇正文的结论在此给出几何解释）：「每步排除」要求当前位置的两个探索方向恰好是「单调性相反」的一对——右上角与左下角恰好各有一个「最大方向」与一个「最小方向」；左上角与右下角的两个方向是「同向单调」（都增或都减），排除逻辑失效。实现选择：两种写法的代码长度与复杂度完全相同——工程上按「矩阵的形状偏好」选（行多列少时从右上出发更早排除列……实际差别微小，选哪个都是对的——对称实现的存在价值是：一个写法出 bug 时，换个对称写法重写，往往能绕过思维定式）。
Z 字查找的「泛化」：从矩阵到任意偏序结构
Z 字查找的「每步排除」思想可以泛化到更抽象的结构：任何偏序结构上的查找，只要能找到一个「极值点」（在该点，所有未排除的元素可以分为「确定大于」和「确定小于」两组），就可以做结构化的排除查找。矩阵的右上角是一个极值点（行最小+列最大的交集），BST 的根是另一个（左子树全小、右子树全大）——两者的共同点是：每个候选点都把搜索空间分成「必然大」和「必然小」的两个不相交子空间——这就是「排除法查找」的结构基础。反面教训：在无序数组上，任何位置都无法安全排除——因为没有偏序结构可以利用。Z 字查找的教训因此超越了矩阵查找：在解决任何查找问题时，先问「这个结构有没有极值点」——有，就找它；没有，就先建结构（排序、建索引）再找——这是从「线性扫描」到「结构化查找」的思维跃迁。
矩阵查找的「分治」进阶
行列有序矩阵的查找还有一个进阶解法值得了解：分治查找。思想：把矩阵分成四个象限，与目标比较左下角或右上角——如果左下角大于目标则排除最下行，如果右上角小于目标则排除最左列——递归地在剩余的三个象限中查找。复杂度分析：每次排除一行加一列，递归深度 O(log(m+n))——与 Z 字查找的 O(m+n) 相比各有优劣（分治在理论上更优但常数更大）。分治的实现复杂度远高于 Z 字查找且在实际工程中很少使用——了解它更多是为了理解分治思想在矩阵上的应用——本库语境里分治是排序与查找的通用范式（快排、归并、Z 字、值域二分都可以用分治的视角统一理解）。
矩阵查找的分治进阶
行列有序矩阵的查找还有一个进阶解法值得了解：分治查找。思想：把矩阵分成四个象限，与目标比较左下角或右上角——如果左下角大于目标则排除最下行，如果右上角小于目标则排除最左列——递归地在剩余的三个象限中查找。复杂度分析：每次排除一行加一列递归深度 O(log(m+n))——与 Z 字查找的 O(m+n) 相比各有优劣。分治的实现复杂度远高于 Z 字查找且在实际工程中很少使用——了解它更多是为了理解分治思想在矩阵上的应用——本库语境里分治是排序与查找的通用范式（快排、归并、Z 字、值域二分都可以用分治的视角统一理解）。
小结
这篇收成四条：右上角（或左下角）是唯一具备「每步确定排除」性质的起点——大于左移排一列、小于下移排一行，O(m+n) 步走完；极角的唯一性源于双重单调的反向性——其他起点无法安全排除；Z 字 vs 逐行二分看矩阵形状——小行大列时二分更快，方阵时 Z 字完胜，「排除率」视角统一了所有查找设计；姊妹题（378 值域二分、旋转数组搜索）共享「每步安全排除一块」的心法——前提永远是结构保证排除的确定性。
参考资料
- LeetCode 240. Search a 2D Matrix II —— 题目与官方题解（含分治进阶解法）
- 本库前篇：《LeetCode 33. 搜索旋转排序数组》《搜索二维矩阵（74）》—— 查找家族的相邻篇目
- LeetCode 378. 有序矩阵中第 K 小的元素 —— 同结构的值域二分变体
读者留言
COMMENTS 暂无还没有留言，来说第一句？