74. 搜索二维矩阵

题意

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。

• 每行的第一个整数大于前一行的最后一个整数。

难度

中等

示例

示例 1：

1677380746702-281e8bf1-90fe-45a0-bf9e-be6fa2911891.jpeg

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true

示例 2：

1677380754774-4e1d67ba-571d-4237-988e-982606ab1d8d.jpeg

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

分析

一开始，我们会想到一个非常直观的算法——遍历整个二维数组，观察 target 是否出现

过。

但是这样子的弊端很明显，如果 target 出现在整个二维数组的最后一个位置，那么所花

费的时间代价是非常巨大的，而这个时间代价显然超出了我们的承受范围。

所以我们需要改进。

我们注意到该矩阵有两个特性：

• 每行中的整数从左到右按升序排列。

• 每行的第一个整数大于前一行的最后一个整数。

参照这两个性质，一个想法便油然而生了——我们能不能把这个二维数组拆成一条链呢？

也就是把题目转化为查找一个一维数组中有没有出现过 target 这个数。

这时候，我们的老朋友——“二分查找”，就能够派上用场了。

首先我们设置两个变量：lef 和 rig。

分别让 lef = 0，rig = n * m - 1。这时候，他们两个代表的就是转化后的一维数组的头跟

尾。

接下来就按照二分查找的基本方法来操作了：取中值，判断中值与 target 的大小关系，

如果比 target 大，则移动 rig，如果小，则移动 lef。而取得中值这一步，就是这个算法

最为关键的地方。我们来观察下图：

1677380761584-0a7429fa-93b7-44a3-8d5d-2ef56ddbc71d.png

这是经过我们对位置编码后的一个 3 * 4 的二维数组，例如一个数 5，我们要确定它的行

号和列号，只需要：$ / 4= 1 $ ，$ 5 % 4 = 1 $，这时候我们就可以知道 5 的位置是

matrix[1][1]了，类比这样的方式，我们就能够非常快速地取得中值。

class Solution {

public boolean searchMatrix(int[][] matrix, int target) {

int lef = 0,rig = matrix.length * matrix[0].length - 1;

while (lef <= rig) {

int mid = lef + (rig - lef) / 2;

if (matrix[mid / matrix[0].length][mid % matrix[0].length] == target)

return true;

if (matrix[mid / matrix[0].length][mid % matrix[0].length] < target)

lef = mid + 1;

else rig = mid - 1;

}

return false;

}

}

同样的，还有另外一种方法，我们先对第一列元素进行二分查找，确定 target 最可能存

在的那一行，在该行中再进行一次二分查找，最终确定是否有 target 存在。

class Solution {

public boolean searchMatrix(int[][] matrix, int target) {

int lef = -1, rig = matrix.length - 1;

while (lef < rig) {

int mid = lef + (rig - lef + 1) / 2;

if (matrix[mid][0] <= target) {

lef = mid;

} else {

rig = mid - 1;

}

}

int posX = lef;

 if (posX < 0) {

System.out.println("SB");

//注意第一次查找就找不到比 target 更小的，则代表 target 不可能存在于 matrix 中

return false;

}

lef = 0;

rig = matrix[posX].length - 1;

while (lef <= rig) {

int mid = lef + (rig - lef) / 2;

if (matrix[posX][mid] == target) {

return true;

} else if (matrix[posX][mid] > target) {

rig = mid - 1;

} else {

lef = mid + 1;

}

}

return false;

}

}

二种方法殊途同归，时间复杂度也是一样的，第一种方法的时间复杂度比较好直接计算，

因为是一次二分查找，所以时间复杂度就是$ O()

，第 二 种 方 法 用 了 两 次 二 分 查 找 ，第 一 次 二 分 查 找 的 时 间 复 杂 度 是

O() ， 第 二 次 二 分 查 找 的 时 间 复 杂 度 是 O()

， 所 以 总 的 时 间 复 杂 度 是 O( + ) = O() $。

1677380768444-e229866f-a919-464b-ba7c-ef064d4e204c.png

总结

本题的关键点在于找到位置转换的秘诀以及将整个二维数组拆分成链，最终才能用上我们

的基本功——二分查找，所以说解题过程就是由灵感+扎实的基本功构成的。而扎实的基

本功能让我们对灵感的捕捉更加敏感，不断锻炼自己的技能，我们也会不断进步。

力扣链接：https://leetcode.cn/problems/search-a-2d-matrix/