原题地址：搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:
输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
二分查找
由于矩阵的行列均有序，可以先用二分查找找到目标所在行，再用二分查找在该行中找到目标。
具体的实现代码如下：
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
const searchMatrix1 = function(matrix, target) {
if (matrix.length === 0) {
return false;
}
let [m, n] = [matrix.length, matrix[0].length];
let [leftM, rightM] = [0, m - 1]; // 二分搜索行的区间
while (leftM <= rightM) {
let middleM = Math.floor((leftM + rightM) / 2 );
// 找到了目标可能在的行
if (target >= matrix[middleM][0] && target <= matrix[middleM][n - 1]) {
let [leftN, rightN] = [0, n - 1]; // 行内二分搜索的区间
while (leftN <= rightN) {
let middleN = Math.floor((leftN + rightN) / 2 );
// 找到了目标
if (target === matrix[middleM][middleN]) {
return true;
}
if (target < matrix[middleM][middleN]) {
// 目标可能在左半区间
rightN = middleN - 1;
} else {
// 目标可能在右半区间
leftN = middleN + 1;
}
}
}
if (target <= matrix[middleM][0]) {
rightM = middleM - 1;
} else {
leftM = middleM + 1;
}
}
return false;
};
测试：
let start = new Date();
const test = searchMatrix1;
console.log(test([
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
], 3)); // true
console.log(test([
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
], 13)); // false
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度： 两次二分查找，时间复杂度为$O(logM)+O(logN)=O(logMN)$
空间复杂度： 常数级额外空间，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 25,2019