问题描述

编写一个高效的算法来搜索 m × n 矩阵 matrix 中的一个目标值 target。

该矩阵具有以下特性：

• 每行的元素从左到右递增排序。
• 每列的元素从上到下递增排序。

格式

输入

• 一个 m × n 的整数矩阵 matrix。
• 一个整数 target，表示需要查找的目标值。

输出

• true：如果 target 在 matrix 中。
• false：如果 target 不在 matrix 中。

样例

样例1

输入

5 5
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
5

输出

true

样例2

输入

5 5
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
20

输出

false

提示

• 1 <= m, n <= 300
• -10⁹ <= matrix[i][j] <= 10⁹
• -10⁹ <= target <= 10⁹