LeetCode 74. 搜索二维矩阵Search a 2D MatrixPython3 实现思路把矩阵视为一维升序数组做二分查找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,nlen(matrix),len(matrix[0])left,right0,m*n-1whileleftright:mid(leftright)//2valmatrix[mid//n][mid%n]ifvaltarget:returnTrueelifvaltarget:leftmid1else:rightmid-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,nlen(matrix),len(matrix[0])# 二分定位候选行找最后一个首元素 target 的行lo,hi0,m-1whilelohi:mid(lohi1)//2ifmatrix[mid][0]target:lomidelse:himid-1rowlo# 在行内二分lo,hi0,n-1whilelohi:mid(lohi)//2ifmatrix[row][mid]target:returnTrueelifmatrix[row][mid]target:lomid1else:himid-1returnFalse推荐使用第一种一维二分写法简洁且常数更小。