企业官网建设流程全解析

LeetCode 74. 搜索二维矩阵（Search a 2D Matrix）Python3 实现

思路：把矩阵视为一维升序数组做二分查找（O(log(m×n))）

• 矩阵每行递增，且每行首元素大于上一行末元素，整体等价于一个长度为 m×n 的有序数组；
• 二分下标mid，映射回二维坐标：row = mid // n, col = mid % n。

fromtypingimportListclassSolution:defsearchMatrix(self,matrix:List[List[int]],target:int)->bool:ifnotmatrixornotmatrix[0]:returnFalsem,n=len(matrix),len(matrix[0])left,right=0,m*n-1whileleft<=right:mid=(left+right)//2val=matrix[mid//n][mid%n]ifval==target:returnTrueelifval<target:left=mid+1else:right=mid-1returnFalse

复杂度

• 时间：O(log(m × n))
• 空间：O(1)

另一种写法：两次二分（先定位行，再在行内二分），也是 O(log m + log n)，思路更直白但代码稍长：

classSolution:defsearchMatrix(self,matrix:List[List[int]],target:int)->bool:ifnotmatrixornotmatrix[0]:returnFalsem,n=len(matrix),len(matrix[0])# 二分定位候选行：找最后一个首元素 <= target 的行lo,hi=0,m-1whilelo<hi:mid=(lo+hi+1)//2ifmatrix[mid][0]<=target:lo=midelse:hi=mid-1row=lo# 在行内二分lo,hi=0,n-1whilelo<=hi:mid=(lo+hi)//2ifmatrix[row][mid]==target:returnTrueelifmatrix[row][mid]<target:lo=mid+1else:hi=mid-1returnFalse

推荐使用第一种一维二分写法，简洁且常数更小。