二维数组中的查找

题目：

在一个 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(1),时间复杂度为 O(n*m)

优化：

题干中有写到“每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序”，这是优化的关键。

因为是有序的，我们可以从右上角开始，右上角这个元素，是 行的最大值， 列的最小值，此时拿来与 target 比较，如果 num 比目标值 大，说明目标值在左边，num 所在的那一行都不用寻找了（舍弃），如果 num 比目标值小，说面 目标值 在下方，此时， num 所在的 行 都不用寻找了，可以舍弃。

实现，设置一个下标 row 为 0，代表第一行， 一个下标 column 为 列长度减一，往左寻找 时 ，列下标减一，往下寻找时，行下标加一，放在循环里面，知道找到为止，找不到 则放回 false。

时间复杂度O(n+m)O(n+m)。访问到的下标的行最多增加 n 次，列最多减少 m 次，因此循环体最多执行 n + m 次。

空间复杂度为O(1)。