【Hot 100 刷题计划】 LeetCode 74. 搜索二维矩阵 | C++ 二分查找 (一维展开法)

LeetCode 74. 搜索二维矩阵 题目描述题目级别中等给你一个满足下述两条属性的m x n整数矩阵每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数target如果target在矩阵中返回true否则返回false。示例 1:输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,60]],target 3输出true 破题思路降维打击化二维为一维这道题虽然披着“二维矩阵”的外衣但由于它满足**“全局严格递增”不仅行内递增且下一行开头大于上一行结尾我们可以直接对它实施降维打击**。如果我们将这个m行n列的矩阵像拉面条一样拉直它就是一个长度为m * n的严格单调递增的一维数组。既然是一维有序数组那寻找目标值最快的方法毫无疑问就是二分查找。本题核心坐标映射魔法在虚拟的一维数组中我们二分出的中间索引是mid。那么这个mid对应回真实的二维矩阵它的行号和列号是多少呢假设矩阵有n列每行有n个元素行号mid / n前面有几个完整的行列号mid % n在当前行里排第几个我们不需要真的去开辟一个一维数组把数据拷出来只需要在脑海中虚拟出这个一维数组并在访问矩阵元素时套用这个公式即可 C 代码实现 (左闭右开二分模板)classSolution{public:boolsearchMatrix(vectorvectorintmatrix,inttarget){intmmatrix.size(),nmatrix[0].size();// 使用左闭右开区间 [0, m * n)intl0,rm*n;while(lr){intmidl(r-l)/2;// 防止溢出的标准写法 (原写法 (lr)/2 逻辑上亦正确)// 核心数学映射一维索引转换为二维坐标intmid_valmatrix[mid/n][mid%n];if(mid_valtarget){returntrue;}elseif(mid_valtarget){lmid1;// 目标在右半边}else{rmid;// 目标在左半边由于是右开区间r 直接等于 mid}}returnfalse;}};