如何在2d数组中搜索从左到右和从上到下排序的数字? [英] How do I search for a number in a 2d array sorted left to right and top to bottom?

问题描述

最近有人问我这个面试问题，我很好奇它会是一个好的解决方案.

I was recently given this interview question and I'm curious what a good solution to it would be.

说我得到一个二维数组，其中所有 数组中的数字不断增加 从左到右，从上到下的顺序 底部.

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)时间中单行中是否存在数字.但是，正是这两个方向使我失望.

Now, my first inclination is to utilize a binary search since my data is sorted. I can determine if a number is in a single row in O(log N) time. However, it is the 2 directions that throw me off.

我认为可行的另一种解决方案是从中间开始.如果中间值小于我的目标，那么我可以确定它位于中间矩阵的左方部分.然后，我沿对角线移动并再次检查，以减小目标可能位于的正方形的大小，直到我确定了目标编号为止.

Another solution I thought may work is to start somewhere in the middle. If the middle value is less than my target, then I can be sure it is in the left square portion of the matrix from the middle. I then move diagonally and check again, reducing the size of the square that the target could potentially be in until I have honed in on the target number.

有人有解决这个问题的好主意吗?

Does anyone have any good ideas on solving this problem?

示例数组:

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

Sorted left to right, top to bottom.

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

推荐答案

以下是一种简单的方法:

Here's a simple approach:

1. 从左下角开始.
2. 如果目标小于该值，则该目标必须高于我们，因此上移一个目标.
3. 否则，我们知道目标不能在该列中，因此向右移动.
4. 转到2.

1. Start at the bottom-left corner.
2. If the target is less than that value, it must be above us, so move up one.
3. Otherwise we know that the target can't be in that column, so move right one.
4. Goto 2.

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

For an NxM array, this runs in O(N+M). I think it would be difficult to do better. :)

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

Lots of good discussion. I was talking about the general case above; clearly, if N or M are small, you could use a binary search approach to do this in something approaching logarithmic time.

对于好奇的人，这里有一些细节:

Here are some details, for those who are curious:

此简单算法称为鞍背搜索.它已经存在了一段时间，当N == M时是最佳选择.一些参考:

This simple algorithm is called a Saddleback Search. It's been around for a while, and it is optimal when N == M. Some references:

• David Gries， 编程科学 . Springer-Verlag，1989 .
• Edsgar Dijkstra， 鞍背搜索 . 注意EWD-934，1985年.

• David Gries, The Science of Programming. Springer-Verlag, 1989.
• Edsgar Dijkstra, The Saddleback Search. Note EWD-934, 1985.

但是，当N < M时，直觉表明二进制搜索应比O(N+M)更好:例如，当N == 1时，纯二进制搜索将以对数而非线性时间运行.

However, when N < M, intuition suggests that binary search should be able to do better than O(N+M): For example, when N == 1, a pure binary search will run in logarithmic rather than linear time.

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

Richard Bird examined this intuition that binary search could improve the Saddleback algorithm in a 2006 paper:

• Richard S. Bird， 改进鞍背搜索:一课 ，<程序设计数学>，第82--89页，第4014卷，2006年.

使用一种非常不寻常的对话技术，Bird向我们展示了对于N <= M，此问题的下界为Ω(N * log(M/N)).这个界限是有道理的，因为它使我们在N == M时具有线性性能，而在N == 1时具有对数性能.

Using a rather unusual conversational technique, Bird shows us that for N <= M, this problem has a lower bound of Ω(N * log(M/N)). This bound make sense, as it gives us linear performance when N == M and logarithmic performance when N == 1.

使用逐行二进制搜索的一种方法如下:

One approach that uses a row-by-row binary search looks like this:

1. 从矩形数组开始，其中N < M.假设N是行，而M是列.
2. 在中间行对value进行二进制搜索.如果找到它，我们就完成了.
3. 否则，我们找到了一对相邻的数字s和g，其中s < value < g.
4. s上方和左侧的数字矩形小于value，因此我们可以消除它.
5. g下方和右侧的矩形大于value，因此我们可以消除它.
6. 针对剩余的两个矩形中的每个，转到步骤(2).

1. Start with a rectangular array where N < M. Let's say N is rows and M is columns.
2. Do a binary search on the middle row for value. If we find it, we're done.
3. Otherwise we've found an adjacent pair of numbers s and g, where s < value < g.
4. The rectangle of numbers above and to the left of s is less than value, so we can eliminate it.
5. The rectangle below and to the right of g is greater than value, so we can eliminate it.
6. Go to step (2) for each of the two remaining rectangles.

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

In terms of worst-case complexity, this algorithm does log(M) work to eliminate half the possible solutions, and then recursively calls itself twice on two smaller problems. We do have to repeat a smaller version of that log(M) work for every row, but if the number of rows is small compared to the number of columns, then being able to eliminate all of those columns in logarithmic time starts to become worthwhile.

这使算法的复杂度为T(N,M) = log(M) + 2 * T(M/2, N/2)，Bird显示为O(N * log(M/N)).

This gives the algorithm a complexity of T(N,M) = log(M) + 2 * T(M/2, N/2), which Bird shows to be O(N * log(M/N)).

Craig Gidney发布的另一种方法描述了一种与该方法相似的算法上图:它使用步长M/N一次检查一行.他的分析表明，这也会导致O(N * log(M/N))性能.

Another approach posted by Craig Gidney describes an algorithm similar the approach above: it examines a row at a time using a step size of M/N. His analysis shows that this results in O(N * log(M/N)) performance as well.

Big-O分析很好，但是这些方法在实践中效果如何?下图检查了越来越多的正方形"阵列的四种算法:

Big-O analysis is all well and good, but how well do these approaches work in practice? The chart below examines four algorithms for increasingly "square" arrays:

(朴素"算法只是搜索数组中的每个元素.上面介绍了递归"算法.混合"算法是

(The "naive" algorithm simply searches every element of the array. The "recursive" algorithm is described above. The "hybrid" algorithm is an implementation of Gidney's algorithm. For each array size, performance was measured by timing each algorithm over fixed set of 1,000,000 randomly-generated arrays.)

一些值得注意的要点:

• 不出所料，二进制搜索"算法在矩形阵列上提供了最佳性能，而Saddleback算法在方形阵列上发挥了最佳性能.
• 对于1-d数组，Saddleback算法的性能比朴素"算法差，这大概是因为它对每个项目进行了多次比较.
• 二进制搜索"算法对正方形数组的性能影响可能是由于运行重复的二进制搜索会产生开销.

巧妙地使用二进制搜索可以为矩形和正方形阵列提供O(N * log(M/N)性能. O(N + M)鞍回"算法要简单得多，但是随着阵列变得越来越矩形，性能会下降.

Clever use of binary search can provide O(N * log(M/N) performance for both rectangular and square arrays. The O(N + M) "saddleback" algorithm is much simpler, but suffers from performance degradation as arrays become increasingly rectangular.

这篇关于如何在2d数组中搜索从左到右和从上到下排序的数字?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！