[B]1.A，B为两个长度为n的有序数组，在O(logn)时间内求A并B的中值（习题集P224，习题7.13）注意这题和06那到真题不一样的。

2.已知定值K和长度为n的数组，在O(n^2)时间内检验是否存在三个数之和为K，这题我怎么想都要O(n^2logn)的时间，郁闷……习题集P225

3.一数组中只有0，1，2三种数，在O(logn)时间内排序，这题和荷兰国旗问题是一样的，我觉得最少也得O(n)那，不知道O(logn)怎么来的……[/B]

PS:我下载了最新的习题指导勘误，这三题都没有。

望有人能给出解答，只要算法思想即可，不必写程序了。谢谢！

第三题我认为不可能在O(logn)的时间能完成。随便找一个反例：如果原始数组是0,1,2,0,1,2,0,1,2,....这样的形式，那么要把它变成有序（无论正序还是倒序）都需要修改O(n)个单元，怎么可能在O(logn)的时间能完成呢？

2提示：先排序，然后固定一个数，其余两个依次二分查找。

如何两次二分查找？固定一个数之后能找第二个数吗？？？

我看是先固定一个数，接下来用递归的方法找到两个数的和满足要求的两个数，我计算过，复杂度为n,所以总的复杂度刚好是n*n。真的不知道怎样写出两个依次二分查找，其复杂度是log(n)*log(n)的

还是你的意思就是我上面那个帖子中的算法？
那就是n*logn*logn呀，第一个数n，剩下两个数均是二分：logn*logn……
对吗？

“用递归的方法找到两个数的和满足要求的两个数”，应该怎么进行？且复杂度是n？

1）a很好办，就是从头开始依次指；
2）当a指定了某一个数后，如果这个数大于k，算法结束；
3）否则考虑b，记b的查找区间下标为bl，br，初始时bl=a+1，br=n-1，b在[bl，br]这个区间内二分查找，直到找到第一个b，使a+b<k，不如果没有找到，考虑下一个a；
4）如果找到，记c的查找区间下标为cl，cr，初始时cl=a+1，cr=n-1，考虑c，c在[cl，cr]这个区间内二分查找，直道找到某一个c，使a+b+c=k，如果没有找到，说明b还是太大了，把br指向b-1，转3）；
5）如果找到，则a，b，c是一个解，现在关键是找下一个解：要考虑让b小一点，c大一点；或者b大一点，c小一点。对于第一种情况：由于[bl，b]中的元素都满足a+b<k，所以要试这中间的每一个b，固定了b后，cl指向c+1，转4）；对于第二种情况，b的取值应该在[b+1，br]中，依次检查这中间的b，直到a+b〉=k，考虑下一个a，否则c在cr=c-1，转4）

btw:应该没有更好的算法了，5）处的实现可以再修改一下，但是效率不能改，否则就丢失解了。

1 3 4 10 19 21 50  K=41,有答案41=1+19+21
a=1,b=10,a+b=11<K,c在3至50中找30，没找到，说明b还是太大了，把br指向b-1,
b=3,c在3至50中找37，未找到，
b不能再减少了，移动a，a=3，
然后b和c都不能取比a小的数，故最后查找失败…………

感觉错误出在4）：为什么说“说明b还是太大了”？根据上例，b其实是太小了，此时a=1，b=10，而答案应该a=1,b=19,c=21。。

是不是应该让bl和cl都从1开始找？为什么要是a+1呢？题目说可以有重复元素啊…。
另外，logician说的我也没注意看，还是n^2logn吗？

显然可以证明2*ai>=ap + aq，若p<=i且q<=i；2*ai<=ap + aq，若p>=i且q>=i；
这样在2*a1~2*an中二分查找r（即在正方形的对角线上进行二分搜索）,使得2*ai <= r <= 2*a(i+1)
由上面的分析可以知道所以的p,q若p<i且q<i或者p>i+1且q>i+1，r!=ap+aq;因此可以在矩阵的其他部分进行查找~假设i=n/2，则一次查找过程在n*n个组合可能去掉了一半的组合可能
令开销函数为T(n*n)， 有T(n*n) = 2*T(n*n/4)+logn  /*可以想象为原正方形一下去掉了2个1/4小正方形，需要对剩下的2个小正方形递归查找 */
由master理论可知，T(n*n) = (n*n)^log4(2) = (n*n)^(1/2) = n
所以总的复杂度为n*n

这是我最初的思路，后来想了想，由于每次查找得到的i不一定是n/2，开销函数应修改为       T(n*n) = 2*T(i*(n-i))+logn ，这样下面的递归也不能在对角线上进行查找， 因此算法需要进行修改，不过我想最终的平均复杂度应该还是n*n；

：）

我想这就是正确答案，星期一想出来的，因为我工作日无法上网，所以一直没公开出来，
不幸的是，今天我又想到了一个反例（其实也不能说是反例），看：

如果在b、c搜索过程中，第一次移b，第二次移c，如此交替，则在此情况下搜索树枝长可能为2logn，但这样的话时间代价为2^(2logn)=n^2…………
又郁闷了。。。

第一题，我想了一种变态的数组情况：
A:11111111111111156
B:11111111111111178
显然中值为6，但似乎不可能在logn时间内找到，如果1的数量极多的话……
但O(n)级的还是很简单的，大家再思考一下吧。