urf*_*end 8 algorithm divide-and-conquer
我们有两个大小为n的数据库,包含没有重复的数字.所以,我们总共有2n个元素.可以通过一次查询到一个数据库来访问它们.查询是这样的,你给它ak,它返回该数据库中的第k个最小的条目.我们需要在O(logn)查询中的所有2n个元素中找到第n个最小的条目.我的想法是使用分而治之,但我需要一些帮助来思考这个问题.谢谢!
这就是我的想法。由于这是一个教育问题，如果其中任何一点让您认为“啊哈，我没有想到这一点，我可以自己沿着这些思路进一步思考”，我建议您停止阅读。
1) 与 sdcwc 的观察相同：对于它是从 0 还是 1 开始可能有一点争议，数据库可以被认为是一个排序数组。我要求元素 0，我得到最小的。我要 12 个，我得到第 13 个最小的。等等。我发现这更容易想象。
2）我们知道我们正在寻找一个 O(log n) 算法。这意味着粗略地说我们正在寻找以下两件事之一：
我们要么从计算最小的元素开始，然后计算第二小的元素、第四小的元素、第八小的元素，等等，直到达到我们想要的大小，每一步都需要恒定的时间。这对我来说听起来不太有希望。
或者我们从一个大小为 n 的问题开始，然后执行一些恒定时间操作，这使我们能够通过解决大小为 n/2 的问题来解决原始问题。显然我们可以在常数时间内解决n=1的问题，从而完成算法。这听起来似乎更合理一些。
实际上不一定每次都是n/2。它可以是 n/3，或者 999*n/1000，结果仍然是 O(log n)。但先寻找 n/2 也没有什么坏处。
3）我们如何减少这样的问题？好吧，如果我们可以从一个数组或另一个数组的开头处折扣/删除 m 个元素，因为它们小于第 k 个最小的元素，那么我们可以找到所得数组对中第 (km) 个最小的元素，它将是原始数组中第 k 个最小的数组。
4) 最后，突破性的观察是，如果数组 A 的第 m 个最小元素小于数组 B 的第 m 个最小元素，则 A 的第 m 个元素不可能是两个数组组合中的第 (2m) 个最小元素。它比这个小（或者具有相同的值：我不确定“无重复”是否意味着“每个数据库中没有重复”，或者“合并的数据库之间没有重复”），因为最多有 2*(m- 1) 两个数组中的元素相加后严格小于它。
除非我犯了错误，否则剩下的就是编码了。当 k 为奇数时，使用一个小的额外参数来解释 off-by-1，该解决方案实际上是 O(log k)，即 O(log n)，因为 k <= 2*n。