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

Question

最近有人问我这个面试问题，我很好奇这个问题有什么好的解决办法。
假设我得到一个二维数组
数组中的数字正在增加
从左到右，从上到下
底部。
什么是最好的搜索方法
确定目标号码是否在
阵列？
现在，我的第一个倾向是使用二进制搜索，因为我的数据是排序的。我可以在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很小，可以使用二进制搜索方法在接近对数时间的情况下执行此操作。
以下是一些细节，供好奇者参考：
历史
这个简单的算法叫做aSaddleback Search。它已经存在了一段时间，当N == M时是最佳的。一些参考资料：
大卫·格里斯，The Science of Programming。斯普林格·维拉格，1989年。
埃德加·迪克斯特拉，The Saddleback Search。注：EWD-9341985。
然而，当N < M时，直觉表明二进制搜索应该比O(N+M)做得更好：例如，当N == 1时，纯二进制搜索将在对数时间而不是线性时间内运行。
最坏情况限制
Richard Bird在2006年的一篇论文中研究了二进制搜索可以改进鞍形算法的直觉：
Richard S.Bird，Improving Saddleback Search: A Lesson in Algorithm Design，程序构造数学，第82-89页，第40142006卷。
bird用一种非常不寻常的会话技巧向我们表明，对于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)。
Another approach posted by Craig Gidney描述了与上述方法类似的算法：它使用O(N * log(M/N))的步长一次检查一行。他的分析表明，这也会导致M/N的性能。
性能比较
Big-O分析是非常好的，但是这些方法在实践中的效果如何下表分析了四种用于日益“平方”的数组的算法：
（“naive”算法只搜索数组的每个元素。上面描述了“递归”算法“混合”算法是Gidney's algorithm的一种实现对于每个数组大小，通过在1000000个随机生成的数组的固定集合上为每个算法计时来衡量性能。）
一些值得注意的地方：
如所料，“二进制搜索”算法在矩形阵列上的性能最好，而鞍形算法在方形阵列上的性能最好。
Saddleback算法的性能比一维数组的“naive”算法差，这可能是因为它对每个项进行了多次比较。
“二进制搜索”算法对方形数组的性能影响可能是由于运行重复二进制搜索的开销所致。
概要
巧妙地使用二进制搜索可以为矩形和方形阵列提供O(N * log(M/N))性能。“鞍背”算法简单得多，但随着阵列变得越来越矩形，性能会下降。