企业官网建设流程全解析

LeetCode 74 “搜索二维矩阵” 要求判断目标值是否存在于一个每行递增且行与行之间也整体递增的矩阵中。

解题思路

由于矩阵具有“每行有序 + 下一行首元素大于上一行尾元素”的特性，它本质上就是一个按行展开后的一维有序数组。因此，最高效的方法是使用二分查找，时间复杂度为
“O(log(m*n))”。

Rust 实现（整体二分查找）

这是最简洁且高效的做法：将
“matrix[i][j]” 映射为一维索引
“mid / cols” 和
“mid % cols”。

impl Solution {
pub fn search_matrix(matrix: Vec<Vec>, target: i32) -> bool {
// 边界情况处理
if matrix.is_empty() || matrix[0].is_empty() {
return false;
}

let rows = matrix.len(); let cols = matrix[0].len(); let mut left = 0; let mut right = rows * cols; // 标准的左闭右开区间二分查找 while left < right { let mid = left + (right - left) / 2; let mid_val = matrix[mid / cols][mid % cols]; if mid_val == target { return true; } else if mid_val < target { left = mid + 1; } else { right = mid; } } false }

}

备选方案：两次二分查找（先找行，再找列）

如果你想更直观地利用矩阵的“行列”结构，可以先通过二分找到
“target” 可能所在的行，再在该行中二分查找。

impl Solution {
pub fn search_matrix(matrix: Vec<Vec>, target: i32) -> bool {
if matrix.is_empty() || matrix[0].is_empty() {
return false;
}

let rows = matrix.len(); let cols = matrix[0].len(); // 1. 二分查找确定目标所在的行 // 利用每行的第一个元素来判断 let mut top = 0; let mut bottom = rows; while top < bottom { let mid = top + (bottom - top) / 2; if matrix[mid][0] <= target { top = mid + 1; } else { bottom = mid; } } // top 是第一个首元素大于 target 的行，所以 target 应该在 top - 1 行 let row = if top > 0 { top - 1 } else { return false; }; // 2. 在该行中使用标准库二分查找 matrix[row].binary_search(&target).is_ok() }

}

复杂度分析

• 时间复杂度：
  “O(log m + log n)” 或
  “O(log(mn))”，两者等价，均为二分查找的对数级效率。
• 空间复杂度：
  “O(1)”，只使用了常数级别的额外变量。

小贴士

• 在 Rust 中，使用
  “binary_search” 会返回
  “Result<usize, usize>”，通过
  “.is_ok()” 可以很方便地判断是否存在。
• 如果矩阵非常大且你希望减少乘法/除法开销，两次二分（利用行列索引）会稍微快一点点，但在 LeetCode 判题机上整体二分已经完全足够且代码更短。

需要我帮你把这个算法改写成不分配额外内存的迭代器版本，或者讲解从右上角开始的 O(m+n) 解法吗？😊