如何在从左到右、从上到下排序的二维数组中搜索数字？

2024-05-04

我最近收到了这个面试问题，我很好奇有什么好的解决方案。

假设我有一个二维数组，其中所有数组中的数字在增加从左到右、从上到下的顺序底部。

搜索和搜索的最佳方式是什么？判断目标号码是否在大批？

现在，我的第一个倾向是使用二分搜索，因为我的数据已排序。我可以在 O(log N) 时间内确定一个数字是否在一行中。然而，这两个方向让我失望。

我认为可能有效的另一个解决方案是从中间的某个地方开始。如果中间值小于我的目标，那么我可以确定它位于矩阵中间的左侧正方形部分。然后，我沿对角线移动并再次检查，减小目标可能所在的正方形的大小，直到我磨练出目标数字为止。

有人对解决这个问题有什么好主意吗？

数组示例：

从左到右、从上到下排序。

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11

这是一个简单的方法：

从左下角开始。
如果目标小于该值，则它一定在我们之上，所以上移一位.
否则我们知道目标不能在该列中，所以向右移动一个.
Goto 2.

For an NxM数组，这运行在O(N+M)。我认为很难做得更好。 :)

Edit:很多很好的讨论。我上面说的是一般情况；显然，如果N or M很小，您可以使用二分搜索方法在接近对数时间内完成此操作。

以下是一些细节，供好奇的人参考：

History

这个简单的算法称为马鞍峰搜索 http://www.cs.geneseo.edu/~baldwin/math-thinking/saddleback.html。它已经存在了一段时间，当它是最佳的N == M。一些参考：

大卫·格里斯,编程科学 https://rads.stackoverflow.com/amzn/click/com/0387964800. 施普林格出版社，1989.
埃兹格·迪杰斯特拉,马鞍峰搜索 http://www.cs.utexas.edu/users/EWD/index09xx.html. 注 EWD-934，1985.

然而，当N < M，直觉表明二分查找应该能够比O(N+M): 例如，当N == 1，纯二分搜索将以对数时间而不是线性时间运行。

最坏情况界限

Richard Bird 在 2006 年的一篇论文中检验了二分搜索可以改进 Saddleback 算法的直觉：

理查德·伯德，改进鞍背搜索：算法设计的一课 http://www.cs.ox.ac.uk/publications/publication2664-abstract.html, 程序构建数学，第 82--89 页，第 4014 卷，2006 年.

伯德使用一种相当不寻常的对话技巧向我们展示了N <= M，这个问题的下界为Ω(N * log(M/N))。这个界限是有道理的，因为它为我们提供了线性性能N == M和对数性能时N == 1.

矩形阵列的算法

一种使用逐行二分搜索的方法如下所示：

从一个矩形数组开始，其中N < M。比方说N是行并且M是列。
对中间行进行二分查找value。如果我们找到它，我们就完成了。
否则我们找到了一对相邻的数字s and g, where s < value < g.
上方和左侧的数字矩形s小于value，所以我们可以消除它。
下面和右侧的矩形g大于value，所以我们可以消除它。
对于剩下的两个矩形，分别转到步骤 (2)。

就最坏情况的复杂度而言，该算法log(M)努力消除一半可能的解决方案，然后在两个较小的问题上递归调用自身两次。我们确实必须重复一个较小的版本log(M)为每一行工作，但如果行数与列数相比较小，那么能够在对数时间内消除所有这些列就开始变得值得.

这使得算法的复杂度为T(N,M) = log(M) + 2 * T(M/2, N/2)，伯德表明是O(N * log(M/N)).

Craig Gidney 发布的另一种方法 http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster描述了一种与上述方法类似的算法：它使用步长大小一次检查一行M/N。他的分析表明，这会导致O(N * log(M/N))性能也是如此。

性能比较

Big-O 分析固然很好，但这些方法在实践中效果如何？下图检查了用于日益“方形”数组的四种算法：

（“朴素”算法简单地搜索数组的每个元素。“递归”算法如上所述。“混合”算法是吉德尼算法 http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster。对于每个数组大小，通过在 1,000,000 个随机生成的固定数组上对每个算法进行计时来测量性能。）

一些值得注意的点：

正如预期的那样，“二分搜索”算法在矩形数组上提供最佳性能，而马鞍形算法在方形数组上效果最佳。
对于一维数组，Saddleback 算法的性能比“朴素”算法差，大概是因为它对每个项目进行多次比较。
“二分搜索”算法对方形数组的性能影响可能是由于运行重复二分搜索的开销造成的。

Summary

巧妙地使用二分查找可以提供O(N * log(M/N)矩形和方形阵列的性能。这O(N + M)“鞍背”算法要简单得多，但随着数组变得越来越矩形，性能会下降。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)