# 搜索二维矩阵
# 难度：简单
# 描述：
写出一个高效的算法来搜索 m × n 矩阵中的值。
这个矩阵具有以下特性：
- 每行中的整数从左到右是从小到大排序的。
- 每行的第一个数大于上一行的最后一个整数。
# 样例：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
1
2
3
4
5
2
3
4
5
给出 target = 3，返回 true
# 题目分析：
双循环找出是否有这个值，根据第二个特性，我们可以跳过一些第二层循环，算法更具效率。
# 代码：
/**
* @param matrix: matrix, a list of lists of integers
* @param target: An integer
* @return: a boolean, indicate whether matrix contains target
*/
const searchMatrix = function(matrix, target) {
for (let key of matrix.keys()) { // 遍历外层数组
let value = matrix[key]; // 拿到每行元素
// 判断target是否在当前行中，跳过其他不必要循环
if (target <= value[value.length - 1]) {
for (let item of value.keys()) { // 遍历行中元素
if (target === value[item]) { // 找到值
return true;
} else if (target < value[item]) { // 值超过target即找不到(因为是排序的)
return false;
}
}
}
}
return false; // 没有找到即返回false
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21