搜索m/n的二维数组中的元素,即行和列

Question

您将获得一个MxN的2D数组,该数组按行和列顺序排序.搜索元素的有效方法是什么？

Answer 1

从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 .
* * * * . .
* * * * . .

现在递归剩下的两件作品.此外,您可以在中间行或左上角到右下角度执行相同的操作,具体取决于哪个将产生最大增益.