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

Question

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

Say I'm given a 2d array where all the numbers in the array are in increasing order from left to right and top to bottom.

What is the best way to search and determine if a target number is in the array?

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

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

有没有人有解决这个问题的好主意？

示例数组:

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

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

Answer 1

这是一个简单的方法:

从左下角开始。

如果目标小于该值，则它必须高于我们，因此 上移一位 .

否则我们知道目标不能在该列中，所以 向右移动一个 .

转到 2。

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

编辑:很多很好的讨论。我说的是上面的一般情况；显然，如果 N或 M小，您可以使用二进制搜索方法在接近对数时间的情况下执行此操作。

以下是一些细节，对于那些好奇的人:

历史

这个简单的算法叫做 Saddleback Search .已经有一段时间了，最​​好的时候是 N == M .一些引用:

大卫·格里斯， The Science of Programming .施普林格出版社，1989 年。

Edsgar Dijkstra, The Saddleback Search .注意 EWD-934，1985。

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

最坏情况界限

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

理查德·伯德， Improving Saddleback Search: A Lesson in Algorithm Design , in Mathematics of Program Construction, pp. 82--89, volume 4014, 2006.

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

矩形阵列的算法

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

从一个矩形数组开始，其中 N < M .比方说 N是行和 M是列。

对 value 的中间行进行二分搜索.如果我们找到它，我们就完成了。

否则我们会找到一对相邻的数字 s和 g ，其中 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)) .

Another approach posted by Craig Gidney描述了一种类似于上述方法的算法:它使用 M/N 的步长一次检查一行。 .他的分析表明，这会导致 O(N * log(M/N))性能也是如此。

性能比较

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



(“天真”算法只是搜索数组的每个元素。“递归”算法在上面描述过。“混合”算法是 Gidney's algorithm 的实现。对于每个数组大小，性能是通过将每个算法计时超过固定时间来衡量的一组 1,000,000 个随机生成的数组。)

一些值得注意的点:

正如预期的那样，“二进制搜索”算法在矩形阵列上提供最佳性能，而 Saddleback 算法在方形阵列上效果最佳。

对于一维数组，Saddleback 算法的性能比“naive”算法差，大概是因为它对每个项目进行了多次比较。

“二分搜索”算法对方形数组的性能影响可能是由于运行重复二分搜索的开销。

总结

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