搜索二维矩阵II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例 1：
codeType
输入：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
示例 2：
codeType
输入：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 = 20
输出：false
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- -109 <= matrix[i][j] <= 109
- 每行的所有元素从左到右升序排列
- 每列的所有元素从上到下升序排列
- -109 <= target <= 109
解法
解法一 直接逐个搜索
解法二 逐行二分搜索
ts
function searchMatrix(matrix: number[][], target: number): boolean {
// 这题没法直接从二维数组映射成一维升序数组，所以没法直接用二分查找
// 但是每行或者每列都是升序的
// 可以逐行进行二分查找
const n = matrix.length
const m = matrix[0].length
for(let i = 0; i < n; i++){
let low = 0, high = m - 1
while(low <= high){
const mid = Math.floor((low + high) / 2)
if(matrix[i][mid] === target){
return true
}else if(matrix[i][mid] < target){
// 在右边
low = mid + 1
}else{
// 在左边
high = mid - 1
}
}
}
return false
};
解法三：z字搜索
ts
function searchMatrix(matrix: number[][], target: number): boolean {
// z字搜索
const m = matrix.length, n = matrix[0].length;
let x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] === target) {
return true;
}
if (matrix[x][y] > target) {
--y;
} else {
++x;
}
}
return false;
};