leetCode ✏基础刷题之(74. Search a 2D Matrix)
.
✏描述
*给定一个顺序排序MN的二维矩阵以及一个目标值，编写一个高效的算法，判断是否存在给定值，如果不存在，返回false。每一行整数从左到右升序，并且下一行的第一个数大于前一行最后一个数。**
✏题目实例
✏题目分析
这里的难点在于矩阵我们咋么像一维数组的位置来表示每一个值的位置，其实是可以转换的，按照我们的想法，10的位置就是4($index)，给定矩阵中每一行的个数4(m),对应的表示如下。你对应带几个数试试看，是不是这个转换公式，道理嘛可以自己想想
$matrix[$index/m][$index % m],
既然这个问题解决了，那就是一个很普通的二分查找了，可以看下之前的文章超级好用的二分模板，开始套上，接下来就是代码了
✏最终实现代码
/**
* @param Integer[][] $matrix
* @param Integer $target
* @return Boolean
*/
function searchMatrix($matrix, $target)
{
$m = count($matrix);
if ($m == 0) return false;
$n = count($matrix[0]);
if ($n == 0) return false;
$left = 0;
$right = $m * $n - 1;
while ($left < $right) {
$middle = ($left + $right) >> 1;
$res = $matrix[$middle / $n][$middle % $n];
if ($res < $target) {
$left = $middle + 1;
} else {
$right = $middle;
}
}
return $matrix[$left / $n][$left % $n] == $target ? true : false;
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)