搜索二维矩阵

算法思路

题目给定的矩阵满足以下两个条件：

• 每行中整数从左到右非严格递增排列；
• 每行的第一个整数大于上一行最后一个整数。

这两个条件说明整个矩阵可以看作一个有序的一维数组。可以将矩阵的下标映射为一维下标，然后使用二分查找算法快速判断目标值是否存在。具体做法如下：

Leetcode 64.搜索二维矩阵-原题链接

题目内容

给你一个满足下述两条属性的 $m×n$整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 $target$ ，如果 $target$ 在矩阵中，输出 $true$ ；否则，输出 $false$。

输入描述

第一行包含两个整数 $m$ 和 $n$，分别表示矩阵的行数和列数。

接下来的 $m$ 行，每行包含 $n$ 个整数，表示矩阵的元素。

最后一行包含一个整数 $target$。

输出描述

如果 $target$ 存在于矩阵中，则输出 true，否则输出 false。输出不用考虑大小写。

样例1

输入

3 4
1 3 5 7
10 11 16 20
23 30 34 60
3

输出

true

样例2

输入

3 4
1 3 5 7
10 11 16 20
23 30 34 60
13

输出

false

提示

• $m == matrix.length$
• $n == matrix[i].length$
• $1 <= m, n <= 100$
• $-10^4 <= matrix[i][j], target <= 10^4$