题目链接：剑指 Offer 04. 二维数组中的查找

题目描述：

在一个 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
复制代码

题目思路：

这个题目是经典的矩阵问题，通过观察我们可以发现题目所示矩阵有这么一个特点：极值都在四角。

就像示例里面的矩阵，左上角为最大值，右下角为最小值。

那么我们解题的思路就可以从这一块入手：

从左下角开始找，通过题目的所给矩阵的递增关系，如果大于就往右边找，如果小于就往上面找，超出矩阵长度则返回false。

解法实现：

1. 首先一步初始化一个flag数组用了记录所有遍历过的元素。
2. 使用过的值需要格式化,代表已经遍历过了，遍历结束后再修改回来。
3. 最后注意要及时break，否则会超时。

func findNumberIn2DArray(matrix [][]int, target int) bool {
    //以左下角为原点
    i:=len(matrix)-1//获取右下角y坐标
    j:=0//获取右下角x坐标
    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{
        //超出数组的话返回false
            return false
        }
    }
    //超出矩阵的话返回false
    return false
}
复制代码

总结：

整体来说不算难，理解了思路之后也很容易自己实现，属于做过一次就会印象深刻的题目。

其实还有一种思路是使用 sort 包下的 SeachInts 方法，然后遍历数组切片。不过这种现成的 API 调用其实不利于我们算法思维的锻炼，就不展开说了,有兴趣的可以去研究研究。