所以，这是一个常见的面试问题。已经有一个主题了，我已经阅读过，但是它已经死了，并且没有人接受任何答案。最重要的是，我的兴趣在于问题的一种稍微更受限制的形式，以及一些实际应用。
给定一个二维数组:
- 元素是独一无二的。
- 元素沿 x 轴和 y 轴排序。
- 两种排序都不占主导地位，因此两种排序都不是次要排序参数。
- 结果，对角线也被排序。
- 可以认为所有类型都朝着同一个方向发展。也就是说它们都是上升的，或者说它们都是下降的。
- 从技术上讲，我认为只要您有一个 >/=/< 比较器，任何总排序都应该有效。
- 元素是数字类型，带有单周期比较器。
- 因此，内存操作是大 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 的唯一编号的 s , 所有 2具有大于 X 的唯一编号的 s , 和 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/