你得到一个 MxN 的二维数组，它是按行和列排序的。搜索元素的有效方法是什么？
问问题
1836 次
3 回答
5
v从矩阵的右上角开始。如果它是x您正在寻找的项目，那么您就完成了。如果v小于您要查找的项目，请向下移动。如果v大于您要查找的项目，请向左移动。重复直到到达矩阵的末端。
正确性证明：
如果右上项等于x，则无需证明。考虑两种情况
v < x
在这种情况下，我们知道顶行中的所有元素都小于x。因此，我们可以忽略整个顶行并向下移动。
因此，我们可以从
1 2 3 4 5 6
1 * * * * * v
2 * * * * * *
3 * * * * * *
4 * * * * * *
5 * * * * * *
至
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 .
* * * * . .
* * * * . .
现在递归剩下的两个部分。此外，您可以在中间行或左上角到右下角对角线执行相同的过程，具体取决于哪个会产生最大收益。
于 2013-08-04T17:36:46.153 回答
2
这里有一个非常好的算法来解决这个问题。正如文章所描述的，对每一行（或同样对每一列）按行进行简单的二进制搜索会给出 O(n log n) 的解决方案。但是，从右上角开始然后线性向左或向下进行的简单算法会导致 O(n) 算法。（没错：线性搜索胜过二分搜索！）然而，更好的结果来自使用矩阵的二分法（基于线性搜索），并导致算法在某些情况下具有 O((log n) 2 ) (次线性）性能。
最好的算法似乎是一种分而治之的方法：对于一个m × n矩阵M，其中n（列数）< m（行数）*和目标值v，搜索中间行（称为行r ) 对于索引c使得M r , c ≤ v < 目标值v是M r , c +1。如果v = M r , c，然后你就完成了。否则，递归地将算法应用于子矩阵M r +1, 0 ...<em>M m -1, c和M 0, c +1 ...<em>M n -1, r。（这些是由单元格 ( r +1, c )包围的左下角矩阵和由单元格 ( r -1, c +1)包围的右上角矩阵。）
有关性能和代码本身的详细信息，请参阅链接。
* 如果n > m，则改为搜索中间列。如果n = m，搜索对角线。每种情况下子矩阵的确切边界需要根据上述描述稍作调整；见文章。
于 2013-08-04T17:43:22.543 回答
0
通常第一个索引是“行”，第二个是“列”，列索引应该是连续内存，即使行是在单独的块中分配的，所以从这个角度来看，搜索一个的所有列应该更快行，然后移动到下一行并迭代那里的列。
显然，这假设您要搜索的所有项目均等分布，并且“每行中的第一项更有可能是您正在寻找的候选人，而每列中的最后一项最不可能”。
同样很明显，如果每一行都包含已排序的值，那么您可以对列进行二进制搜索，如果最小值和最大值未覆盖您正在搜索的范围，则可以跳过整行。
与“更快”的所有事情一样，您确实需要对您的解决方案进行基准测试，以确定在您的特定情况下什么是最好的。
于 2013-08-04T17:37:24.580 回答