个人评价：二维数组，通常暴力破解方式就是嵌套循环，但通常可进一步优化~
题目难度：🌟🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）
另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章
二维数组中的查找
题目描述
剑指 Offer 04. 二维数组中的查找 240. 搜索二维矩阵 II
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
解题思路
先不考虑数组的排序规则，不难想到暴力方式，行+列遍历，复杂度？🙌 O(n*m) 空间 O(1)
方法一
如果只是单纯的考虑行排序，不难想到二分查找：
- 比如某一行的第一个元素大于 target ，当前行和后边的所有行都不用考虑了，直接返回 false
- 某一行的最后一个元素小于 target ，当前行就不用考虑了，换下一行
代码实现暂略，复杂度？O(m)*O(logn)
列排序是不是没有用到？？没错，再想想其他方式
方法二
二维数组类似矩阵，数组有个很好的特性是根据下标查找时间复杂度 O(1)，数组长度已知，无论从左至右还是从右直左都是可行的。放置二维，从上到下，从下到上也👌。
那，考虑题目中的排序，怎样可以更高效地找到目标数？不从左上，我们从左下开始思考。
从左下开始，target 若小则向上找（i–）；若大，则向右找（j++）；Go 实现代码参考如下：
func findNumberIn2DArray(matrix [][]int, target int) (res bool) {
i := len(matrix)-1
j := 0
for i > -1 {
if j < len(matrix[i]) {
if target < matrix[i][j] {
i-- //target小,向上查找
} else if target > matrix[i][j] {
j++ //targat大,向右查找
} else if target == matrix[i][j] {
return true
}
} else {
return false //超出数组返回false
}
}
return false //超出matrix返回false
}
你也可以从右上开始查找，target 大向左；target小向下。只是初始化需要注意数组为空的情况
https://goplay.tools/snippet/7sMntXWmzm9 Go play~
复杂度分析？
🙌 时间复杂度：O(n+m)。访问到的下标的行最多增加 n 次，列最多减少 m 次。空间 O(1)
暴力查找是全覆盖，而这种查找方式则可想象为线性查找
总结
数组的随机查找是很具有优势的，数组不光可以从左往右，从右往左也是可行的。
二维数组是很神奇的，甚至可以转置，左下或者右上的思考方式还是值得借鉴的。