教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是 AlgoNote「算法通关手册」针对力扣LeetCode第 74 题「搜索二维矩阵Search a 2D Matrix」的完整题解。该题属于「数组、二分查找、矩阵」三类标签的组合题型被收录在仓库的 二分查找题目列表 与 面试 200 题清单 中是二分查找从一维数组向二维矩阵迁移的经典入门题。阅读完本文你将掌握逐行逐列同时升序矩阵的二分可行性分析、对角线分治 行列二分的完整实现以及区间开闭、mid 取值等二分细节在本解法中的具体运用。一、题目概述描述给定一个 $m \times n$ 大小的有序二维矩阵 $matrix$。矩阵中每行元素从左到右升序排列每列元素从上到下升序排列。再给定一个目标值 $target$。要求判断矩阵中是否存在目标值 $target$存在返回True不存在返回False。说明$m matrix.length$。$n matrix[i].length$。$1 \le m, n \le 100$。$-10^4 \le matrix[i][j], target \le 10^4$。示例示例 1输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 3 输出True示例 2输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 13 输出False二、有序矩阵的二分可行性分析一维二分查找参见仓库基础文档 01_13 二分查找一成立的前提是数据有序。本题矩阵具备两个方向的单调性行内有序第 $i$ 行满足 $matrix[i][0] \le matrix[i][1] \le \dots \le matrix[i][n-1]$列内有序第 $j$ 列满足 $matrix[0][j] \le matrix[1][j] \le \dots \le matrix[m-1][j]$。更关键的是本题的矩阵满足逐行连续升序第 $i$ 行最后一个元素 $matrix[i][n-1]$ 一定小于第 $i1$ 行第一个元素 $matrix[i1][0]$。因此整个矩阵按行展开后等价于一个长度为 $m \times n$ 的一维升序数组——这正是 0074 与 0240搜索二维矩阵 II的本质区别后者只保证每行从左到右、每列从上到下局部有序但第 $i$ 行末元素不一定小于第 $i1$ 行首元素无法直接展开成一维。基于以上单调性可以对矩阵实施二分查找。仓库本题解 search-a-2d-matrix.md 给出的核心思路是先二分对角线锁定分界位置再在分界附近的行与列上分别二分。三、解题思路对角线分治 行列二分3.1 总体框架二分对角线假设对角线元素坐标为 $(row, col)$即 $matrix[row][col]$其中 $row col$。利用矩阵两个方向的单调性在对角线上二分查找 $target$ 的落点把矩阵按对角线划分为右上角部分与左下角部分。行二分对于当前对角线元素右侧的第 $row$ 行进行一次行内二分查找。列二分对于当前对角线元素下侧的第 $col$ 列进行一次列内二分查找。终止条件若在任一行或列中找到目标直接返回True若所有可能的对角线位置都已尝试仍未找到返回False。3.2 对角线二分diagonalBinarySearchdef diagonalBinarySearch(self, matrix, diagonal, target): left 0 right diagonal while left right: mid left (right - left) // 2 if matrix[mid][mid] target: left mid 1 else: right mid return left该函数在 $0 \sim diagonal$diagonal min(rows, cols) - 1的对角线元素上找到第一个满足 $matrix[mid][mid] \ge target$的下标 $index$。这里采用的是二分查找中的「排除法」写法详见 01_14 二分查找二 的排除法一节当 $matrix[mid][mid] target$ 时说明目标值只可能出现在右下方向排除左上半区令left mid 1否则目标值可能在左上方向含当前对角线元素收缩右边界right mid。由于循环条件为left right循环结束时必有left right此时left就是对角线上的分界下标。3.3 行二分rowBinarySearchdef rowBinarySearch(self, matrix, begin, cols, target): left begin right cols while left right: mid left (right - left) // 2 if matrix[begin][mid] target: left mid 1 elif matrix[begin][mid] target: right mid - 1 else: left mid break return begin left cols and matrix[begin][left] target在第begin行内、下标区间 $[begin, cols]$ 上查找 $target$。注意查找的左端点从begin开始而不是从 0 开始——这是利用了矩阵的单调性对角线左下方区域的元素必然小于目标值无需重复搜索从而把每轮查找区间进一步压缩。命中时通过break提前退出最后用begin left cols and matrix[begin][left] target做一次边界合法性与值相等的收尾校验。3.4 列二分colBinarySearchdef colBinarySearch(self, matrix, begin, rows, target): left begin 1 right rows while left right: mid left (right - left) // 2 if matrix[mid][begin] target: left mid 1 elif matrix[mid][begin] target: right mid - 1 else: left mid break return begin left rows and matrix[left][begin] target与行二分对称在第begin列内、下标区间 $[begin 1, rows]$ 上查找。左端点取begin 1是因为对角线元素 $matrix[begin][begin]$ 已在行二分或主函数中处理过避免重复比较。返回值同样是下标合法且值相等的布尔判断。3.5 主函数searchMatrixdef searchMatrix(self, matrix: List[List[int]], target: int) - bool: rows len(matrix) if rows 0: return False cols len(matrix[0]) if cols 0: return False min_val min(rows, cols) index self.diagonalBinarySearch(matrix, min_val - 1, target) if matrix[index][index] target: return True for i in range(index 1): row_search self.rowBinarySearch(matrix, i, cols - 1, target) col_search self.colBinarySearch(matrix, i, rows - 1, target) if row_search or col_search: return True return False主函数做了三件事空矩阵守卫先处理rows 0与cols 0的空矩阵边界直接返回False对角线二分定界min_val min(rows, cols)取行、列较小者保证对角线索引合法调用diagonalBinarySearch得到分界下标index若对角线上直接命中target则返回True分界附近逐行逐列二分对 $i \in [0, index]$ 的每个对角线位置同时在该行与列上二分任一侧命中即返回True全部遍历完仍无命中则返回False。四、完整代码将上述各函数整合为完整可运行的解法与仓库 search-a-2d-matrix.md 中收录的实现一致from typing import List class Solution: # 二分查找对角线元素 def diagonalBinarySearch(self, matrix, diagonal, target): left 0 right diagonal while left right: mid left (right - left) // 2 if matrix[mid][mid] target: left mid 1 else: right mid return left def rowBinarySearch(self, matrix, begin, cols, target): left begin right cols while left right: mid left (right - left) // 2 if matrix[begin][mid] target: left mid 1 elif matrix[begin][mid] target: right mid - 1 else: left mid break return begin left cols and matrix[begin][left] target def colBinarySearch(self, matrix, begin, rows, target): left begin 1 right rows while left right: mid left (right - left) // 2 if matrix[mid][begin] target: left mid 1 elif matrix[mid][begin] target: right mid - 1 else: left mid break return begin left rows and matrix[left][begin] target def searchMatrix(self, matrix: List[List[int]], target: int) - bool: rows len(matrix) if rows 0: return False cols len(matrix[0]) if cols 0: return False min_val min(rows, cols) index self.diagonalBinarySearch(matrix, min_val - 1, target) if matrix[index][index] target: return True for i in range(index 1): row_search self.rowBinarySearch(matrix, i, cols - 1, target) col_search self.colBinarySearch(matrix, i, rows - 1, target) if row_search or col_search: return True return False代码细节剖析两种二分写法的混用diagonalBinarySearch采用「排除法」循环条件left right结束时left right直接作为答案而rowBinarySearch/colBinarySearch采用「直接法」一旦命中break退出否则在循环内收缩left/right。这与 01_14 二分查找二 中总结的两种思路对应直接法适合目标明确存在、三分支好写的场景排除法适合寻找边界位置的场景这里要找对角线上第一个 $\ge target$ 的位置。防溢出写法三个辅助函数统一使用mid left (right - left) // 2避免left right可能带来的整型溢出问题Python 虽无溢出风险但该写法在 C/C/Java 中同样安全属于 01_14 二分查找二 推荐的统一写法。搜索区间裁剪行二分左边界从begin开始、列二分左边界从begin 1开始充分利用对角线分治后左下方必小于目标的性质每次二分都跳过不可能区间这与「减而治之」的二分思想一脉相承。越界保护行、列二分结束后均以begin left cols或rows先校验下标合法性再取值比较防止二分收缩后left越界导致下标异常。五、复杂度分析仓库 search-a-2d-matrix.md 给出的复杂度结论为时间复杂度$O(\log m \log n)$其中 $m$、$n$ 分别是矩阵的行数和列数。空间复杂度$O(1)$。需要说明的是从代码结构看主循环会对 $i \in [0, index]$ 的每个位置各执行一次行二分与列二分其中 $index \le min(m, n) - 1$因此最坏情况下的时间上界也可以表达为 $O(\min(m, n) \times (\log m \log n))$。仓库中同思路的姊妹题 0240 搜索二维矩阵 II 正是标注了后者这一更保守的复杂度可互为印证。两种表述的差异仅在于对对角线二分定界后实际需要遍历的对角线数量的假设不同读者可结合数据规模理解。整个搜索过程仅使用常数个指针变量空间复杂度为 $O(1)$。六、变式对比0074 与 0240、面试题 10.09本题解与仓库中另外两篇矩阵搜索题解共享同一套对角线 行列二分框架但适用条件不同题目仓库题解矩阵性质能否展开为一维二分0074 搜索二维矩阵search-a-2d-matrix.md行内、列内升序且逐行连续升序可以0240 搜索二维矩阵 IIsearch-a-2d-matrix-ii.md行内、列内升序行与行之间不保证连续不可以面试题 10.09 排序矩阵查找sorted-matrix-search-lcci.md与 0240 相同不可以对 0074 而言因为矩阵按行展开后是一维升序数组还可以采用更直接的通用做法将二维坐标 $(i, j)$ 映射为一维下标 $idx i \times n j$在 $[0, m \times n)$ 上做一次标准二分对应 01_13 二分查找一 中的经典实现时间复杂度 $O(\log(mn))$。该做法实现最简洁但只适用于本题这种逐行连续升序的矩阵一旦遇到 0240 / 面试题 10.09 那样只保证局部有序的矩阵就必须回到对角线分治框架这正是掌握本节思路的价值所在。七、总结与延伸「搜索二维矩阵」是一道把一维二分查找推广到二维的经典题目值得记住三个要点先验证单调性二分的前提是数据有序务必先确认矩阵行、列方向的单调性以及逐行连续这一关键性质对角线是天然的二维分治轴利用对角线元素 $matrix[k][k]$ 的单调性先锁定分界再对分界附近的行与列做二次二分是处理二维有序问题的通用套路细节决定成败区间的开闭选择、mid的取整方向、left mid 1/right mid的收缩配对直接决定是否会死循环或漏解这些细节的系统梳理可继续阅读仓库文档 01_14 二分查找二。在此基础上推荐继续练习仓库内收录的二分查找系列题目如 0035 搜索插入位置、0033 搜索旋转排序数组 与 0240 搜索二维矩阵 II并在 二分查找题目列表 中查看完整训练清单逐步建立起一维 → 二维 → 旋转数组的二分查找能力体系。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐algorithm-base 二分查找变体系列在二维矩阵中应用二分查找LeetCode 74 搜索二维矩阵全解algorithm base 二分查找变体系列在二维矩阵中应用二分查找LeetCode 74 搜索二维矩阵全解 导读 本文是 algorithm base文档教程知识库AlgoNote「算法通关手册」二分查找算法详解——从减而治之思想到有序数组搜索实战AlgoNote「算法通关手册」二分查找算法详解——从减而治之思想到有序数组搜索实战 二分查找Binary Search是《算法通关手册》数组章节中第一个教程文档知识库AlgoNote 算法通关手册二叉搜索树BST查找、插入、创建与删除全攻略AlgoNote 算法通关手册二叉搜索树BST查找、插入、创建与删除全攻略 导读 本文是 AlgoNote 算法通关手册 https://link.git教程文档知识库上一篇10分钟掌握.NET DLL合并il-repack完整使用指南下一篇IDM试用期重置工具使用指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考