在一个m/n的二维数组中查找元素，其中m代表行数，n代表列数，涉及到IT技术。

Question

在一个m/n的二维数组中查找元素，其中m代表行数，n代表列数，涉及到IT技术。

c++calgorithmsearch

3

你被给定一个行和列都按序排列的MxN二维数组。有什么高效的方法来搜索一个元素？

- user2650877

1

你能否提供一些你确切想要做的示例吗？ - NREZ

我不理解“按行和列排序”的含义。是指第k行的所有元素都小于第k+1行的所有元素，且每一行都已经排序了吗？如果是这样的话，你可以在扁平化的数组上进行一维二分搜索——假设原始数组是完整的。 - Adrian Ratnapala

1

列/行范围是否重叠？ - Jason C

1

@AdrianRatnapala - 每行单独查看都是已排序的。每列单独查看也是已排序的。对值没有其他限制（行和/或列范围可以重叠；可能存在重复元素）。 - Ted Hopp

可能是搜索已排序的二维矩阵的重复问题。 - RiaD

3个回答

2

这是一个关于解决该问题的算法的非常好的介绍在这里。正如文章所述，对于每一行（或每一列），通过简单的二分查找可以得到一个O(n log n)的解决方案。然而，从右上角开始线性地向左或向下遍历的简单算法可以得到一个O(n)的算法。（没错：线性搜索胜过二分查找！）然而，更好的结果来自于使用基于线性搜索的矩阵二分法，这个算法在某些情况下具有O((log n)²)（次线性）的性能表现。

最佳算法似乎是采用分治法：对于一个大小为 m × n 的矩阵 M，其中 n（列数）＜m（行数）^*，以及目标值 v，在中间行（称之为第 r 行）中搜索索引 c，使得 M_{r, c} ≤ v ＜ M_{r, c+1} 且目标值 v 不等于 M_{r, c}。如果 v = M_{r, c}，则查找结束。否则，将算法递归应用于子矩阵 M_r+1,0…M_m-1,c 和 M_0,c+1…M_n-1,r。（这些矩阵分别由单元格（r+1，c）定义的左下角矩阵和单元格（r-1，c+1）定义的右上角矩阵构成。）

请参阅链接以了解性能和代码本身的详细信息。

* 如果n > m，则搜索中间列。如果n = m，则搜索对角线。每种情况下子矩阵的确切边界需要稍微调整上述描述；请参见文章。

- Ted Hopp

那太美了。 - jason

0

通常第一个索引是“行”，第二个索引是“列”，即使行分配在不同的块中，列索引也应该是连续的内存，因此从这个角度来看，搜索一个行的所有列然后移动到下一行并迭代那里的列应该更快。

显然，这假定您正在搜索的所有项都是平均分布的，“每行的第一项最有可能是您要寻找的候选项，而每列的最后一项最不可能”。

也很明显，如果每行包含已排序的值，则可以通过列进行二进制搜索，以及在最小值和最大值未涵盖您正在搜索的范围时跳过整行。

与任何“更快”的事情一样，您真的需要对您特定情况下的解决方案进行基准测试以确定什么最好。

- Mats Petersson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jason · Accepted Answer

从矩阵的右上角位置 v 开始。如果它是你要找的元素 x，搜索完成。如果 v 比你要找的元素小，向下移动。如果 v 比你要找的元素大，向左移动。重复此过程直到到达矩阵的边缘。

正确性证明：

如果右上角的元素等于 x，则无需证明。考虑两种情况：

v < x

在这种情况下，我们知道顶行中的所有元素都小于x。因此，我们可以忽略整个顶行并向下移动。

因此，我们可以从以下内容开始：

  1 2 3 4 5 6
1 * * * * * v
2 * * * * * *
3 * * * * * * 
4 * * * * * *
5 * * * * * *

to

  1 2 3 4 5 6
1 . . . . . .
2 * * * * * v
3 * * * * * * 
4 * * * * * *
5 * * * * * *

也就是说，我们最终得到了一个更小的问题。

另一种情况是

v > x

在这种情况下，我们知道右列中的所有元素都大于x。因此，我们可以忽略整个右列并向左侧移动。

  1 2 3 4 5 6
1 * * * * * v
2 * * * * * *
3 * * * * * * 
4 * * * * * *
5 * * * * * *

为了

  1 2 3 4 5 6
1 * * * * v .
2 * * * * * .
3 * * * * * .
4 * * * * * .
5 * * * * * .

再次，我们面临一个较小的问题。通过归纳法，我们完成了任务。这个算法的时间复杂度为O(m + n)。

编辑：

Ted Hopp链接到了这个想法的一个绝妙扩展，可以获得更好的性能。

这里是这个想法。在我上面给出的算法中，思路是我们可以一次性消除整行或整列的考虑。他所链接的思路是一次性消除整个象限。这个想法很简单。

* * * * * *
* * * * * *
* * * * * * <- binary search
* * * * * *
* * * * * *

对中间行进行二分查找。这将为您提供所需的项，或者是包含您要查找的项的位置。

* * * * * *
* * * * * *
* * * a|b * <- x between a, b
* * * * * *
* * * * * *

现在关键的洞见在于，可以立即从考虑范围中排除整个左上象限和整个右下象限；左上角的所有元素都小于a，右下角的所有元素都大于b。

. . . . * *
. . . . * *
. . . a|b .
* * * * . .
* * * * . .

现在对剩下的两个部分进行递归操作。此外，您可以对中间行或左上到右下对角线执行相同的过程，具体取决于哪一个会产生最大的收益。