两个二分法的问题
有两个关于分治演算问题，
第一个，有两个数据库，各自有n个数据，可以分别在单个数据库中进行这样的操作，叫一个数k，表示找到第kth个小的数据，但只局限在单数据库中。现在需要找到这两个数据库数据的中间的数据，也就是第n个数据。
第二个，有n个卡片，他们可能有相同的，有一个检验卡片的机器，每次仅仅能放两个卡片进去进行检验是否相同，现希望能判断是否存在这样的卡片，在n个卡片中有超过n／2个卡片是相同的，要求在O(nlogn)完成。
没有什么好的思路，还请赐教，谢谢。
问题点数：20、回复次数：4Top
1 楼fflush（stdin）回复于 2006-10-02 09:23:39 得分 0
第一题可参考
http://community.csdn.net/Expert/topic/4961/4961354.xml?temp=.1632959
第二题可参考
http://community.csdn.net/Expert/topic/5050/5050300.xml?temp=.9392359
ps第二题实际上可以在O(n)下完成Top
2 楼struggling_wang（）回复于 2006-10-02 23:14:36 得分 0
打不开两个连接，xml解析问题。。。
Top
3 楼LiChenYue（卐)(李忱悦)(怎堪蔑拒？鳄泪横流㊣暗恋未遂！独孤求偶)(卐）回复于 2006-12-05 21:08:55 得分 0
看不懂！Top
4 楼shunan（什么是技术）回复于 2006-12-05 21:42:33 得分 0
第一个问题实际上就是，每次找各自数据库中的中间值，比较这两个值，大的那个数据库把它后面的一半数否决掉，小的那个数据库把它前面的一半否决掉，每次可以否去一半，时间复杂度为O(lgn)Top
