编写一个 高效的算法 来搜索 m × n 矩阵 matrix 中的目标值 target。该矩阵具有以下特性：
m 和 n，表示矩阵的行数和列数。（1 ≤ m, n ≤ 300）m 行，每行输入 n 个整数，表示矩阵的元素。（-10^9 ≤ matrix[i][j] ≤ 10^9）target，表示要搜索的目标值。（-10^9 ≤ target ≤ 10^9）true 或 false，表示是否在矩阵中找到 target。5 5
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
5
true
5 5
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
20
false
本题要求 高效搜索，最优解法为 "Z 字型查找"，时间复杂度 O(m + n)。
核心思路：
由于矩阵
行递增、列递增
，我们可以从
右上角
（或
左下角
）出发：
matrix[i][j] == target，返回 true。> target，左移（j--）。< target，下移（i++）。若超出矩阵边界，则返回 false。
时间复杂度
m + n 步，故 O(m + n)。#include <iostream>
#include <vector>
using namespace std;
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) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) j--; // 向左移动
else i++; // 向下移动
}
return false;
}
int main() {
int m, n, target;
cin >> m >> n;
vector<vector<int>> matrix(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
cin >> target;
cout << (searchMatrix(matrix, target) ? "true" : "false") << endl;
return 0;
}
def search_matrix(matrix, target):
"""
Z 字型搜索矩阵
"""
if not matrix:
return False
m, n = len(matrix), len(matrix[0])
i, j = 0, n - 1 # 从右上角开始
while i < m and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1 # 向左移动
else:
i += 1 # 向下移动
return False
if __name__ == "__main__":
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(m)]
target = int(input())
print("true" if search_matrix(matrix, target) else "false")
import java.util.Scanner;
public class Main {
public static 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) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) j--; // 向左移动
else i++; // 向下移动
}
return false;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt(), n = scanner.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
int target = scanner.nextInt();
scanner.close();
System.out.println(searchMatrix(matrix, target) ? "true" : "false");
}
}