所以，这是一个常见的面试问题。已经有一个话题了，我已经读过，但它已经死了，没有人接受任何答案。最重要的是，我的兴趣在于问题的一种稍微受限的形式，以及一些实际应用。给定一个二维数组，使得: 元素是唯一的。 元素沿 x 轴和 y 轴排序。 两种排序都不占优势，因此两种排序都不是次要排序参数。 结果对角线也排序了。 所有种类都可以被认为是朝着同一个方向移动。也就是说，都是在上升，或者说，都是在下降。 从技术上讲，我认为只要你有一个 >/=/ 元素是数字类型，带有单周期比较器。 因此，内存操作是 big-O 分析中的主导因素。 你如何找到一个元素？只有最坏情况分析才重要。我知道的解决方案:多种方法，分别是:O(nlog(n))，分别处理每一行。O(nlog(n)) 具有很强的最佳和平均性能。一个是 O(n+m):从一个非极端的角落开始，我们假设它是右下角。让目标是 J。 Cur Pos 是 M。如果 M 大于 J，则向左移动。如果 M 小于 J，则向上移动。如果您两者都做不到，那么您就完成了，并且 J 不在场。如果 M 等于 J，你就完成了。最初在别处发现，最近从 here 窃取。我相信我见过最坏情况为 O(n+m) 但最佳情况接近 O(log(n)) 的情况。我好奇的是:现在，我已经满意地证明了朴素分区攻击总是转移到 nlog(n)。分区攻击通常似乎有一个 O(n+m) 的最优最坏情况，并且大多数在不存在的情况下不会提前终止。因此，我还想知道，插值探针是否可能不比二元探针更好，因此我想到有人可能会将其视为集合之间具有弱交互作用的集合交集问题。我的思绪立即转向 Baeza-Yates intersection ，但我没有时间起草该方法的改编版。然而，鉴于我怀疑 O(N+M) 最坏情况的最优性是可证明的，我想我会继续在这里问，看看是否有人可以提出反驳，或者将递归关系放在一起用于插值搜索。 最佳答案 这是一个证明，它必须至少是 Omega(min(n,m)) 。让 n >= m 。然后考虑包含所有 0 的矩阵，其中 (i,j) 的 i+j < m ，所有 2 的 i+j >= m ，除了具有 (i,j) 的 i+j = m 的单个 1 。这是一个有效的输入矩阵，并且 m 有 1 可能的位置。没有对数组的查询(除了 1 的实际位置)可以区分那些 m 可能的位置。因此，您必须在最坏的情况下检查所有 m 位置，并且至少要检查任何随机算法的 m/2 预期位置。您的假设之一是矩阵元素必须是唯一的，而我没有这样做。但是，它很容易修复，因为您只需选择一个大数字 X=n*m ，用小于 0 的唯一编号替换所有 X ，用大于 2 的唯一编号替换所有 X ，并用 1 替换 X 。并且因为它也是 Omega(lg n) (计数参数)，所以它是 Omega(m + lg n) 其中 n>=m 。关于algorithm - 重温 : 2D Array Sorted Along X and Y Axis，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4495013/
