在行和列排序的矩阵中搜索

引言

搜索矩阵中的元素是许多应用程序（从图像处理到数据库）的基本计算机科学问题。当面对一个在行和列上都已排序的矩阵时，我们可以使用更复杂的搜索技术来最大化效率。我们将探讨在行和列排序的矩阵中进行搜索的复杂性，并考察简单和复杂的算法以找到最佳解决方案。

考虑一个二维矩阵，其中每一行和每一列都按升序排列。这种特殊的结构提供了丰富的探索机会和挑战，需要创造性的搜索算法。在这样的矩阵中，传统的搜索技术（如线性搜索）效率低下。因此，开发人员会采用更高级的技术来利用矩阵的排序特性。

行和列排序的矩阵中搜索的算法

从矩阵的右上角开始

从矩阵的右上角元素开始搜索。选择这个角落的原因是它可以有效地根据目标值剔除行或列。

如果找到匹配元素，则返回其位置

检查目标值是否与矩阵中的当前元素匹配。如果匹配，则找到了目标的位置，搜索成功。要么将位置标记为找到，要么返回它。

如果当前元素大于目标，则向左移动

如果当前元素大于目标，则意味着该列中的所有元素都大于目标。为了在同一行中查找较小的值，向左移动。

如果当前元素小于目标值，则向下移动

如果当前元素小于目标值，则意味着该行中的所有元素都小于目标值。为了在同一列中查找较大的值，向下移动。

重复步骤 2-4，直到找到目标或超出边界

重复步骤 2 到 4，直到找到目标或搜索无效。到达矩阵的左边缘或底边缘意味着目标不在矩阵中，这称为越界。

蛮力法

在矩阵中查找目标元素的简单技术是蛮力法。此方法涉及逐一遍历矩阵中的每个元素，直到找到目标。虽然此方法的时间复杂度为 O(m * n)，其中 m 是行数，n 是列数，但存在更有效的方法，尤其适用于大型矩阵。

代码

输出

代码解释

searchMatrixBruteForce 函数

• 参数： 函数接收一个整数 target，表示要搜索的值，以及一个二维数组 matrix，表示矩阵。
• 返回类型： 如果找到目标，则返回一个整数；否则返回 0。

主函数 (main)

• 初始化矩阵： 一个名为 matrix 的 4x4 矩阵，其初始值均为整数。

• 目标值： 整数变量 target 表示要在矩阵中搜索的值，已设置为 5。
• 函数调用： matrix 和 target 作为参数传递给 searchMatrixBruteForce 函数。
• 输出： 程序根据结果打印目标是否找到。

蛮力法（searchMatrixBruteForce）

searchMatrixBruteForce 函数使用嵌套循环遍历矩阵的每个元素。它检查目标值是否与当前元素相等。如果找到匹配项，函数返回 1，表示目标在矩阵中。如果在遍历整个矩阵后未找到匹配项，则函数返回 0，表示目标不存在。

时间复杂度

searchMatrixBruteForce 函数的时间复杂度为 O(m * n)，其中 m 表示矩阵的行数，n 表示矩阵的列数。这是因为代码使用嵌套循环遍历矩阵的每个元素，在最坏的情况下需要检查每个元素。

空间复杂度

无论输入大小如何，该算法只需要固定的额外空间；因此，空间复杂度为 O(1)。仅使用目标、结果和循环计数器（i 和 j）等变量。这些变量所需的空间量是恒定的，并且不会随着输入矩阵的大小而增加。

二分查找法

在行和列都排序的矩阵中查找元素提供了不同的可能性和挑战。虽然蛮力法可能很简单，但在处理大型矩阵时效率可能不高。这时二分查找法可以提供一种利用矩阵排序结构的优化解决方案。二分查找是一种经典的算法技术，通过反复将搜索空间分成两半来高效地查找排序集合中的目标元素。当应用于行和列排序的矩阵时，二分查找可以大大减少所需的比较次数，从而实现 O(m + n) 的时间复杂度，其中 m 是行数，n 是列数。

二分查找在排序矩阵中的工作原理

初始化指针： 应通过将指针设置为矩阵的右上角或任何其他合理的起始点来初始化指针。例如，将 col 设置为 cols - 1，将 row 设置为 0。

与目标进行比较： 将目标与当前位置的元素进行比较。

调整指针： 根据比较结果，通过向左移动（如果当前元素大于目标）或向下移动（如果当前元素小于目标）来调整指针。

重复： 重复步骤 2 和 3，直到找到目标或指针越过边界。

代码

输出

代码解释

函数（searchMatrixBinary）定义

• 为了在行和列都已排序的矩阵中进行二分查找，定义了 searchMatrixBinary 函数。
• 它的参数是一个整数 target 和一个二维数组 matrix。
• 在此示例中，矩阵假定为 4x4（行 = 4，列 = 4）。
• 如果找到目标，函数返回 1；否则返回 0。

设置主函数

• 主函数初始化了一个名为 matrix 的 4x4 矩阵，并包含示例值。
• 要搜索的目标元素设置为 5。

函数调用（searchMatrixBinary）

• 将提供的矩阵和目标作为参数传递给 searchMatrixBinary 函数。
• 结果存储在 result 变量中。

输出

• 然后，根据 result 的值，程序会打印出目标是否在矩阵中找到。

时间复杂度

该代码的时间复杂度为 O(m + n)，其中 m 表示矩阵的行数，n 表示矩阵的列数。这是因为在 while 循环的每次迭代中，根据目标与当前矩阵元素的比较结果，会剔除一行或一列。在最坏的情况下，算法只会遍历每一行和每一列一次，从而得到线性时间复杂度。

空间复杂度

该代码的空间复杂度为 O(1)。无论输入矩阵的大小如何，算法使用的空间量始终相同。仅使用用于索引（row 和 col）和当前元素（currentElement）的整数变量。该算法不使用任何与输入大小成比例的额外数据结构；相反，这些变量占用恒定的空间。