搜索二维矩阵
题目要求
你需要处理的是一个特殊的 m x n 整数矩阵，这个矩阵有两个关键的属性：
- 矩阵的每一行都是非严格递增的，即每一行的元素从左到右可能相等或者递增。
- 矩阵的每一行的第一个元素都比上一行的最后一个元素要大。
你的任务是判断一个给定的整数 target 是否存在于这个矩阵中。如果存在，返回 true；如果不存在，返回 false。
解题思路
这个问题可以通过二分查找来解决，因为矩阵的两个属性使得它的每一行和每一列都是有序的。这意味着我们可以在矩阵的行和列上应用二分查找算法。
首先，我们可以对矩阵的行进行一次二分查找，确定 target 可能所在的行。由于每行的第一个元素都比上一行的最后一个元素大，我们可以比较 target 和每行最后一个元素的大小，来缩小搜索范围。
一旦我们确定了 target 可能所在的行，我们就可以在这一行上进行二分查找，来确定 target 是否存在于该行中。由于行内元素是非严格递增的，这一步也是可行的。
整个过程中，我们需要注意处理边界条件，确保不会出现索引越界的错误。
总结一下，解题步骤如下：
- 对矩阵的行使用二分查找，找到
target可能所在的行。 - 在确定的行内使用二分查找，查找
target是否存在。 - 如果在任一步骤中找到了
target，返回true。 - 如果两次二分查找都没有找到
target，返回false。
这种方法的时间复杂度是 O(log(m) + log(n))，其中 m 是矩阵的行数，n 是矩阵的列数。
Golang 版本
package main
import "fmt"
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
m, n := len(matrix), len(matrix[0])
// 二分查找可能的行
top, bot := 0, m-1
for top <= bot {
row := (top + bot) / 2
if target > matrix[row][n-1] {
top = row + 1
} else if target < matrix[row][0] {
bot = row - 1
} else {
// 二分查找目标行中可能的列
l, r := 0, n-1
for l <= r {
mid := (l + r) / 2
if target > matrix[row][mid] {
l = mid + 1
} else if target < matrix[row][mid] {
r = mid - 1
} else {
return true
}
}
return false
}
}
return false
}
func main() {
matrix := [][]int{
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 60},
}
target := 3
fmt.Println(searchMatrix(matrix, target)) // 输出: true
}
这段代码定义了一个函数 searchMatrix，它接受一个整数矩阵和一个目标值 target 作为参数，返回一个布尔值表示 target 是否在矩阵中。主函数 main 中包含了一个示例矩阵和目标值，用于调用 searchMatrix 函数并打印结果。
C++版本
#include <iostream>
#include <vector>
bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int top = 0, bot = m - 1;
// 二分查找可能的行
while (top <= bot) {
int row = top + (bot - top) / 2;
if (target > matrix[row][n - 1]) {
top = row + 1;
} else if (target < matrix[row][0]) {
bot = row - 1;
} else {
// 二分查找目标行中可能的列
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (target > matrix[row][mid]) {
l = mid + 1;
} else if (target < matrix[row][mid]) {
r = mid - 1;
} else {
return true;
}
}
return false;
}
}
return false;
}
int main() {
std::vector<std::vector<int>> matrix = {
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 60}
};
int target = 3;
std::cout << std::boolalpha << searchMatrix(matrix, target) << std::endl; // 输出: true
return 0;
}
这段 C++代码定义了一个函数 searchMatrix，它接受一个整数矩阵和一个目标值 target 作为参数，并返回一个布尔值表示 target 是否在矩阵中。main 函数中包含了一个示例矩阵和目标值，用于调用 searchMatrix 函数并打印结果。
Python 版本
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
top, bot = 0, m - 1
# 二分查找可能的行
while top <= bot:
row = (top + bot) // 2
if target > matrix[row][-1]:
top = row + 1
elif target < matrix[row][0]:
bot = row - 1
else:
# 二分查找目标行中可能的列
l, r = 0, n - 1
while l <= r:
mid = (l + r) // 2
if target > matrix[row][mid]:
l = mid + 1
elif target < matrix[row][mid]:
r = mid - 1
else:
return True
return False
return False
# 示例
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
target = 3
print(searchMatrix(matrix, target)) # 输出: True
Java 版本
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length, n = matrix[0].length;
int top = 0, bot = m - 1;
// 二分查找可能的行
while (top <= bot) {
int row = (top + bot) / 2;
if (target > matrix[row][n - 1]) {
top = row + 1;
} else if (target < matrix[row][0]) {
bot = row - 1;
} else {
// 二分查找目标行中可能的列
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (target > matrix[row][mid]) {
l = mid + 1;
} else if (target < matrix[row][mid]) {
r = mid - 1;
} else {
return true;
}
}
return false;
}
}
return false;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] matrix = {
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 60}
};
int target = 3;
System.out.println(solution.searchMatrix(matrix, target)); // 输出: true
}
}
这段 Java 代码定义了一个名为 Solution 的类，其中包含了一个 searchMatrix 方法，用于判断目标值 target 是否存在于矩阵 matrix 中。main 方法用于演示如何调用 searchMatrix 方法并打印结果。
Rust 版本
fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool { if matrix.is_empty() || matrix[0].is_empty() { return false; } let (m, n) = (matrix.len(), matrix[0].len()); let (mut top, mut bot) = (0, m as i32 - 1); // 二分查找可能的行 while top <= bot { let row = ((top + bot) / 2) as usize; if target > matrix[row][n - 1] { top = row as i32 + 1; } else if target < matrix[row][0] { bot = row as i32 - 1; } else { // 二分查找目标行中可能的列 let (mut l, mut r) = (0, n as i32 - 1); while l <= r { let mid = ((l + r) / 2) as usize; if target > matrix[row][mid] { l = mid as i32 + 1; } else if target < matrix[row][mid] { r = mid as i32 - 1; } else { return true; } } return false; } } false } fn main() { let matrix = vec![ vec![1, 3, 5, 7], vec![10, 11, 16, 20], vec![23, 30, 34, 60], ]; let target = 3; println!("{}", search_matrix(matrix, target)); // 输出: true }
这段 Rust 代码定义了一个函数 search_matrix，它接受一个整数矩阵和一个目标值，然后判断目标值是否存在于矩阵中。main 函数创建了一个示例矩阵和目标值，调用 search_matrix 函数，并打印结果。
总结
上述解法采用了二分查找的策略来优化搜索效率。首先，我们确定了矩阵的行数和列数，然后使用二分查找来确定目标值可能所在的行。由于矩阵的行是按非递减顺序排列的，我们可以通过比较目标值与当前行的首尾元素来判断目标值是否可能位于该行。
一旦确定了可能的行，我们再次应用二分查找法来确定目标值是否存在于该行的列中。这一步同样利用了列的非递减特性，通过比较目标值与中间元素的大小来缩小搜索范围，直至找到目标值或确定目标值不存在。
这种方法的时间复杂度为 O(log m + log n)，其中 m 是矩阵的行数，n 是矩阵的列数。这比简单的线性搜索要高效得多，特别是在处理大型矩阵时。
在不同的编程语言版本中，虽然语法有所不同，但核心算法和逻辑是一致的。每种语言都需要处理好边界条件，确保不会出现数组越界等错误。通过这种方法，我们可以高效地在一个特定的矩阵中搜索一个目标值。