搜索二维矩阵 II

编写一个高效的算法，在 m x n 矩阵中搜索一个目标值 target。

该矩阵有如下特性：

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

约定

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• -10^9 <= matrix[i][j], target <= 10^9

输入

• matrix：二维矩阵
• target：目标值

输出

矩阵中存在 target 返回 true，否则返回 false。

示例一

输入：

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

示例二

输入：

matrix = 同上
target = 20

输出：

false

复杂度要求

• 时间复杂度：O(m + n)
• 空间复杂度：O(1)