我们得到了数组a [1..n] [1..n]和值x。如果符合以下内容，我们将称呼数组的增加：
对于每个k，l a [k] [l]> = a [i] [j]，其中i＆lt; = k，j＆lt; = l。
我们也被认为是一个正在增加的事实。
任务是证明，没有算法能够确定x在少于n比较中是否是a的元素。
我发现自己完全陷入了那个，所以我很感谢任何帮助。
我证明至少对于一个矩阵，您的n比较最坏，为此，我创建了一个特定的矩阵a。
考虑从[1] [n]到A [n] [1]的对角线线，这包括所有值
A[i][j] for i+j=n+1
将所有元素设置在该对角线的左侧为0：
A[i][j]=0 for i+j<n+1
以及包括对角线本身在内的所有剩余元素至2：
A[i][j]=2 for i+j>=n+1
您可以轻松检查这是根据所需条件的有效矩阵。现在，您可以将对角线上的任何值设置为1：
A[z][n+1-z] = 1
结果看起来像这样：
0 0 0 2
0 0 2 2
0 1 2 2
2 2 2 2
这仍然是有效的矩阵。现在搜索x = 1。为了检查对角线上的任何值是否为1，您必须查看每个值，因为它们是独立的。对角线上有n个值，您必须检查每个值以找到1个值，因此您需要进行n个比较。
@pentadecagon上的变体：您可以自由地在对角线上设置n个任意值，在某个范围内。一侧，另一侧高于最大。
侧面的值无法为您提供有关X位置的信息，n值不给彼此提供任何信息。因此，您需要在n个未分类元素之间进行搜索。