74. 搜索二维矩阵 (Medium)
专题归类： 09-二分查找 · 03-数组与矩阵 LeetCode 链接： https://leetcode.cn/problems/search-a-2d-matrix/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
编写一个高效的算法来判断 m x 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
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
题目详细分析
数据范围含义：
m, n <= 100：暴力 O(mn) 最多 10000 次，也可以过，但题目要求”高效算法”暗示要用 O(log(mn))。- 值范围 [-10^4, 10
矩阵的特殊性质：
- 每行内部升序。
- 下一行的最小值大于上一行的最大值。
- 这意味着整个矩阵可以展开成一个一维有序数组！
核心问题转化： 因为矩阵的”下一行最小 > 上一行最大”，整个矩阵实际上是”蛇形有序”的。将二维坐标映射到一维索引，就是一个标准的一维二分查找。
与 240-搜索二维矩阵 II 的区别：
- 240 题只保证每行升序、每列升序，但不保证”下一行最小 > 上一行最大”，所以不能用一维二分展开，而是用”右上角搜索法”。
小白版直白理解
就像一个大书架，有 m 层（行），每层有 n 本书（列）。书的摆放规则是：
- 每一层从左到右越来越厚（编号递增）。
- 下一层最薄的书也比上一层最厚的书厚。
你可以在脑子里把这个书架想象成一整条长龙：把第一层的书全部取下来，接上第二层、第三层……就得到了一条完全按厚度排序的长队伍。然后在长队伍里用”翻字典法”（二分查找）找目标书。
解题思路
思路一：将二维展开为一维进行二分查找（推荐）
核心思想： 把 m x n 的矩阵看作长度为 m x n 的一维有序数组。通过数学映射在 O(log(mn)) 时间内完成查找。
映射关系：
- 一维索引
mid→ 二维坐标(row, col)：row = mid // ncol = mid % n
可视化（以 3x4 矩阵为例，展平后索引对应关系）：
矩阵:
[ 1, 3, 5, 7] → 索引 0~3
[10, 11, 16, 20] → 索引 4~7
[23, 30, 34, 60] → 索引 8~11
展平为一维: [1,3,5,7,10,11,16,20,23,30,34,60]
索引: 0 1 2 3 4 5 6 7 8 9 10 11
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
# 一维索引 → 二维坐标
row = mid // n
col = mid % n
val = matrix[row][col]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False思路二：两次二分（先找行，再找列）
核心思想： 先用二分查找确定 target 可能在哪一行（找最后一个首元素 <= target 的行），再在该行中二分查找。
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
# 第一步：确定目标行
# 找第一个 matrix[row][0] > target 的行，它的前一行就是目标行
top, bottom = 0, m - 1
while top <= bottom:
mid = top + (bottom - top) // 2
if matrix[mid][0] == target:
return True
elif matrix[mid][0] < target:
top = mid + 1
else:
bottom = mid - 1
# bottom 是最后一个首元素 <= target 的行
row = bottom
if row < 0: # target 比所有行的首元素都小
return False
# 第二步：在目标行中二分查找
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
if matrix[row][mid] == target:
return True
elif matrix[row][mid] < target:
left = mid + 1
else:
right = mid - 1
return False时间复杂度： O(log m + log n) = O(log(mn)) 空间复杂度： O(1)
易错点
- 矩阵为空：
matrix = []或matrix = [[]]时需提前返回 false。 - 一维展开时的列数 n：
mid // n和mid % n中的 n 是列数（不是行数），写反会导致完全错误的坐标。 - 两次二分中”找行”的边界：
bottom指向最后一行首元素 <= target 的行。如果bottom < 0，说明 target 比所有行的首元素都小，直接返回 false。 - 索引从 0 开始：一维索引范围是
[0, m*n-1]，right = m * n - 1是正确的，不要写成m * n。 - 列数为 1 的情况：
n = 1时，mid % 1 = 0，此时矩阵退化为列向量，二分仍然正确。
框架提炼
二维矩阵的一维二分模板：
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
val = matrix[mid // n][mid % n]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False适用条件： 此模板仅适用于”下一行最小 > 上一行最大”的严格递增矩阵。
矩阵二分 vs 搜索的两种思路：
| 方法 | 时间复杂度 | 适用条件 |
|---|---|---|
| 展平一维二分 | O(log(mn)) | 行间严格递增（本题） |
| 两次二分 | O(log m + log n) | 行间严格递增 |
| 右上角搜索 | O(m + n) | 仅每行/每列递增（240题） |
关联题目
- 240-搜索二维矩阵II — 矩阵仅保证每行升序、每列升序，但不能展开为一维有序数组，需要用”右上角搜索法”，O(m+n) 时间。
- 33-搜索旋转排序数组 — 一维数组上的二分变体，与本题的”有序空间”二分思想一脉相承。
- 35-搜索插入位置 — 最基础的一维二分查找，熟练掌握后解决本题的一维展开就非常自然。
- 34-在排序数组中查找元素首末位置 — 二分边界查找的进阶应用，与本题的一维二分核心相同。