二分查找篇——搜索二维矩阵【LeetCode】遍历法

 74. 搜索二维矩阵

双层循环遍历法

一、算法逻辑（逐步通顺讲解每一步思路）

该算法的目标是判断一个给定的目标值 target 是否存在于二维矩阵 matrix 中。

题目给定的矩阵有如下两个特性：

1. 每行元素从左到右升序排列；

2. 每行的第一个整数大于前一行的最后一个整数（整个矩阵可以视作一个升序的「一维数组」）。

然而，这段代码 没有利用上述性质，而是采取了最简单直接的方式：

✅ 1️⃣ 获取矩阵维度

M = len(matrix)：总行数；
N = len(matrix[0])：每行列数。

✅ 2️⃣ 遍历整个矩阵

使用两个嵌套循环，逐个元素遍历二维数组中的每一项：

• 外层循环遍历每一行；

• 内层循环遍历每一列。

✅ 3️⃣ 逐个比对元素值

如果当前元素 matrix[i][j] 等于 target，直接返回 True；否则继续查找。

✅ 4️⃣ 未找到则返回 False

所有元素遍历完后未找到目标值，返回 False。

---

二、核心点总结

该算法核心非常简单直接：

• ✅ 暴力穷举法：遍历整个二维数组逐个比对元素；

• ❌ 未利用矩阵的有序特性，没有进行任何剪枝或优化；

• ✅ 实现简单，容易理解；

• ❌ 对于大数据量输入效率较低。

换句话说，这是最基础的解法（Baseline），适合初学者理解，但在面试或实际场景中不推荐使用。

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:M, N = len(matrix), len(matrix[0])for i in range(M):for j in range(N):if matrix[i][j] == target:return Truereturn False

三、时间复杂度分析

共 M 行，每行 N 个元素：

✅ 时间复杂度为 O(M × N)

---

四、空间复杂度分析

该算法仅使用了常数级别的辅助变量（i, j, M, N），不依赖任何额外数据结构或递归栈：

✅ 空间复杂度为 O(1)

---

✅ 总结一句话

这是一种最朴素的暴力搜索解法，时间复杂度为 O(M×N)，空间复杂度 O(1)，实现简单但未利用矩阵的有序性质，适合新手理解，不适合实际使用或面试场景，可进一步优化为「逐行二分查找」或「二维 -> 一维映射 + 二分」的高效解法。