74. 搜索二维矩阵
题目描述
输入一个 m x n 的整数矩阵 matrix 和整数 target。矩阵满足两点：每一行从左到右单调不减；每一行开头的数都比上一行末尾的数大。
换句话说，把各行首尾相接，就得到一个有序序列。
如果 target 出现在矩阵中，返回 true，否则返回 false。算法的时间复杂度要求为 O(log(m * n))。
示例 1
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
解释：3 在第 0 行。
示例 2
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
解释：13 介于 11 和 16 之间，矩阵里没有它。
数据范围
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
解题思路：一次二分查找（展平为一维）
将矩阵映射为一维数组二分。
为什么正确
候选区间始终包含答案。
复杂度分析
时间 O(log(mn))，额外空间 O(1)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def searchMatrix(self,a,t):
if not a or not a[0]:return False
m,n=len(a),len(a[0]);l,h=0,m*n-1
while l<=h:
x=(l+h)//2;v=a[x//n][x%n]
if v==t:return True
if v<t:l=x+1
else:h=x-1
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length, l = 0, h = m * n - 1;
while (l <= h) {
int x = (l + h) / 2, v = matrix[x / n][x % n];
if (v == target) return true;
if (v < target) l = x + 1;
else h = x - 1;
}
return false;
}
}class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size(), l = 0, h = m * n - 1;
while (l <= h) {
int x = (l + h) / 2, v = matrix[x / n][x % n];
if (v == target) return true;
if (v < target) l = x + 1;
else h = x - 1;
}
return false;
}
};func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
m, n := len(matrix), len(matrix[0]); l, h := 0, m*n-1
for l <= h {
x := (l + h) / 2; v := matrix[x/n][x%n]
if v == target {
return true
}
if v < target {
l = x + 1
} else {
h = x - 1
}
}
return false
}var searchMatrix = function(matrix, target) {
if (!matrix.length || !matrix[0].length) return false;
let m = matrix.length, n = matrix[0].length, l = 0, h = m * n - 1;
while (l <= h) {
const x = (l + h) >> 1, v = matrix[Math.floor(x / n)][x % n];
if (v === target) return true;
if (v < target) l = x + 1;
else h = x - 1;
}
return false;
};function searchMatrix(matrix: number[][], target: number): boolean {
if (!matrix.length || !matrix[0].length) return false;
let m = matrix.length, n = matrix[0].length, l = 0, h = m * n - 1;
while (l <= h) {
const x = (l + h) >> 1, v = matrix[Math.floor(x / n)][x % n];
if (v === target) return true;
if (v < target) l = x + 1;
else h = x - 1;
}
return false;
}其他解法
展平二分利用了“整个矩阵按行拼接后有序”，O(log(mn)) 最快；右上角排除只要求行、列各自有序，更通用，但需要 O(m+n)。
解法 2：右上角出发排除（Z 字形查找） 时间 O(m+n)，空间 O(1)
从右上角开始。当前元素是所在行的最大值、所在列的最小值：如果它大于 target，整列都大于 target，向左移一列；如果小于 target，整行都小于 target，向下移一行；相等就找到了。每一步都会排除一行或一列，最多走 m+n 步。
只依赖行内递增、列内递增，所以也能解第 240 题这种更弱的条件。本题条件更强，O(m+n) 比二分的 O(log(mn)) 慢。
class Solution:
def searchMatrix(self, matrix, target):
m, n = len(matrix), len(matrix[0])
i, j = 0, n - 1
while i < m and j >= 0:
v = matrix[i][j]
if v == target:
return True
if v > target:
j -= 1
else:
i += 1
return Falseclass Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = 0, j = n - 1;
while (i < m && j >= 0) {
int v = matrix[i][j];
if (v == target) return true;
if (v > target) j--;
else i++;
}
return false;
}
}class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int i = 0, j = n - 1;
while (i < m && j >= 0) {
int v = matrix[i][j];
if (v == target) return true;
if (v > target) j--;
else i++;
}
return false;
}
};func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := 0, n-1
for i < m && j >= 0 {
v := matrix[i][j]
if v == target {
return true
}
if v > target {
j--
} else {
i++
}
}
return false
}var searchMatrix = function(matrix, target) {
const m = matrix.length, n = matrix[0].length;
let i = 0, j = n - 1;
while (i < m && j >= 0) {
const v = matrix[i][j];
if (v === target) return true;
if (v > target) j--;
else i++;
}
return false;
};function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length, n = matrix[0].length;
let i = 0, j = n - 1;
while (i < m && j >= 0) {
const v = matrix[i][j];
if (v === target) return true;
if (v > target) j--;
else i++;
}
return false;
}