一天一道算法题（32）：搜索二维数组

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数target，如果target在矩阵中，返回true；否则，返回false。

你必须编写一个时间复杂度为O(log(m * n))的解决方案。

示例 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

四种解题思路

接下来我会带着你，从 O(m·n) 一步步优化到 O(log(m·n))。

第一种：暴力枚举（O(m·n)）

嵌套 for 循环逐个判断，都没匹配就返回 false。这种做法一定会超时，也不符合题目要求，这里不展开。

第二种：逐行二分（O(m·log n)）

对每一行各做一次二分查找。这是最常见的优化思路，但它适用于“行与行之间整体不保证严格递增”的情况——比如下一行第一个元素不一定大于上一行最后一个元素。而这道题的二维数组整体是严格升序的，所以这个做法还不够，需要继续优化。

第三种：两次二分（O(log m + log n) = O(log(m·n))）

从这里开始，才是这道题能 AC 的解法。

思路是：第一次二分确定 target 如果存在，应该在哪一行；第二次二分在这一行里继续找。两次二分就能定位到 target。

• Java 代码演示

classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){introwIndex=binarySearchFirstColumn(matrix,target);if(rowIndex<0){returnfalse;}returnbinarySearchRow(matrix[rowIndex],target);}publicintbinarySearchFirstColumn(int[][]matrix,inttarget){intlow=-1,high=matrix.length-1;while(low<high){intmid=(high-low+1)/2+low;if(matrix[mid][0]<=target){low=mid;}else{high=mid-1;}}returnlow;}publicbooleanbinarySearchRow(int[]row,inttarget){intlow=0,high=row.length-1;while(low<=high){intmid=(high-low)/2+low;if(row[mid]==target){returntrue;}elseif(row[mid]>target){high=mid-1;}else{low=mid+1;}}returnfalse;}}作者：力扣官方题解 链接：https://leetcode.cn/problems/search-a-2d-matrix/solutions/688117/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

• Golang 代码演示

funcsearchMatrix(matrix[][]int,targetint)bool{iflen(matrix)==0||len(matrix[0])==0{returnfalse}m,n:=len(matrix),len(matrix[0])// 第一次二分：定位行// 找第一个满足 matrix[row][n-1] >= target 的行top,bottom:=0,m-1fortop<bottom{mid:=top+(bottom-top)/2ifmatrix[mid][n-1]<target{top=mid+1}else{bottom=mid}}row:=top// 第二次二分：在该行内查找left,right:=0,n-1forleft<=right{mid:=left+(right-left)/2ifmatrix[row][mid]==target{returntrue}elseifmatrix[row][mid]<target{left=mid+1}else{right=mid-1}}returnfalse}

第四种：模拟一维数组

如果把二维数组按元素个数“摊平”，对上面那个 3×4 的数组来说，几乎所有人都会把第一行第一个元素当作第 1 个元素，把第三行第四个元素当作第 12 个元素。我们就按这个逻辑模拟一维数组——整个数组长度为 12。

那问题来了：怎么把这个“脑海中模拟的一维数组”和真实的二维数组做映射？

这里直接给公式：

matrix[mid / n][mid % n]
稍微推演一下就能明白：mid / n 定位行，mid % n 定位列。

好，现在按这个思路写代码。

Java 代码演示

classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){intm=matrix.length,n=matrix[0].length;intlow=0,high=m*n-1;while(low<=high){intmid=(high-low)/2+low;intx=matrix[mid/n][mid%n];if(x<target){low=mid+1;}elseif(x>target){high=mid-1;}else{returntrue;}}returnfalse;}}作者：力扣官方题解 链接：https://leetcode.cn/problems/search-a-2d-matrix/solutions/688117/sou-suo-er-wei-ju-zhen-by-leetcode-solut-vxui/来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Golang 代码演示

funcsearchMatrix(matrix[][]int,targetint)bool{m,n:=len(matrix),len(matrix[0])l,r:=0,m*n-1forl<=r{mid:=l+(r-l)/2ifmatrix[mid/n][mid%n]==target{returntrue}elseifmatrix[mid/n][mid%n]<target{l=mid+1}else{r=mid-1}}returnfalse}

总结

本文是 《算法题目解析系列》 的第 [32] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。