题目内容

给定一个规模为 $m \times n$ 的整数矩阵 matrix，以及一个整数 target。请设计一个高效的搜索方法，判断 target 是否出现在 matrix 中。

该矩阵具有两条单调性：

• 每一行中，越靠右的元素越大；
• 每一列中，越靠下的元素越大。

约束条件：

• 行数 m 与列数 n 均不小于 1，且不大于 300。
• matrix 中的每个元素以及 target 的绝对值都不超过 $10^9$。

输入描述

输入包含两个参数：

• matrix：一个二维整数数组，表示待搜索的矩阵。
• target：一个整数，表示需要查找的目标值。

输出描述

返回一个布尔值。如果 target 存在于 matrix 中，则返回 true；否则返回 false。

样例1

输入

3 3
-5 -2 3
-4 0 5
-1 1 7
0

输出

true

说明

搜索从右上角开始。右上角元素为 3，因为 $3 > 0$，所以向左移动到 -2。此时 $-2 < 0$，所以向下移动到 0。当前元素等于目标值 0，因此返回 true。矩阵中确实包含目标 0。

样例2

输入

1 1
42
42

输出

true

说明

矩阵只有 1 行 1 列，唯一元素为 42。目标值也是 42，因此返回 true。这是最小规模的边界情况。

样例3

输入

1 4
2 4 6 8
5

输出

false

说明

搜索从右上角开始。右上角元素为 8，因为 $8 > 5$，向左移动到 6。此时 $6 > 5$，继续向左移动到 4。因为 $4 < 5$，按搜索规则需要向下移动，但矩阵只有一行，下方没有元素，搜索结束，因此返回 false。