关于Young氏矩阵中存在性问题2

经过朋友的提醒加上一番思索，发现Young氏矩阵的存在性问题确实存在线性时间复杂度的解法，主要感谢IF童鞋的帮忙，在此再来讨论该问题，如果你直接看到了这篇文章，你可能需要先看一下该分类（C++分类）下的《关于Young氏矩阵中存在性问题》，正如题目所示《关于Young氏矩阵中存在性问题2》，本文是对Young氏矩阵的再讨论。

为了便于说明，让我们从百度上海研究院2010年实习生招聘笔试题入手，再来说《算法导论》中的课后习题，两者的不同仅仅在于笔试题里专考虑杨氏方阵。

有如下一个杨氏方阵：

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

而我们要搜索的值为N。

因为是方阵，所以我们能够很方便地找到该方阵对角线上的值，在上面的举例中，对角线应该是1,6,9,12，我们并不像以前那样在边上进行二分查找，而是直接在对角线上进行二分查找，如果找到了，那么算法也就结束了，如果比最小的还小，或者比最大的还大，那么算法也结束了。

如果N=10，那么它就正好在9与12之间，所以以9为右下角的矩阵和以12为左上角矩阵都被排除了，我们只需要判断10是否存在于6,9,10和是否存在于4,9,10中，当然这是一个递归的过程。仔细想想会发现，不管N为何值，一次对角线上的二分查找，就至少能排除掉一半的元素，在上面的例子中，当N在6与9之间时，就正好排除了一半元素。只剩下：

5 7
6 9

和

3 4
8 9

所以最差情况下，我们都能得到如下的关系式：T(n)=2*T(n/2)+log(n)，因为n^log2(2)=n > log(n)，所以上式的解为T(n)=O(n)。

不过这里也存在一个问题，如果矩阵不为一个方阵，而只是一个矩阵，正如《算法导论》中提到的那样，那么我们就无法找到一条对角线了！

很遗憾，当发现有正解后，不觉感到上面所有的讨论都是多余甚至是无聊的，答案远比想象中简单的多：

总是于最右上角的元素x比较；

1. 如果==x,结束；
2. 如果比x小，那么元素只可能在前N-1列中；
3. 如果比x大，那么元素只可能在后M-1行中

young氏矩阵去掉一行或一列还是young氏矩阵；所以每次比较最少去掉一行或一列，这样复杂度就是O(m+n)。

最后看来，我承认我做了相当多的无用功！