我们有两个大小为n的数据库,包含没有重复的数字.所以,我们总共有2n个元素.可以通过一次查询到一个数据库来访问它们.查询是这样的,你给它ak,它返回该数据库中的第k个最小的条目.我们需要在O(logn)查询中的所有2n个元素中找到第n个最小的条目.我的想法是使用分而治之,但我需要一些帮助来思考这个问题.谢谢!
algorithm divide-and-conquer
algorithm ×1
divide-and-conquer ×1