将n组数据排序为一组

Question

我有n个数据数组，每个数组都按照相同的标准排序。

阵列的数量在几乎所有情况下都不会超过10个，所以它是一个相对较小的数字。然而，在每个数组中，可以是大量的对象，对于我所寻找的算法应该视为无限大。我现在想要将这些数组看作是一个数组。但是，我确实需要一种方法，尽可能快地检索给定范围内的对象，而不必触摸范围之前的所有对象和/或范围之后的所有对象。因此，它不是迭代所有对象并将它们存储在单个数组中的选项。具有低起始值的提取也比起始值高的提取更有可能。所以例如获取对象[20,40]比获取对象[1000,1020）更可能发生，但可能发生。

范围本身将非常小，约20个对象，或者可以增加，如果与性能相关，只要这不会达到内存限制。所以我猜想几百个物体也可以。

示例： 3个阵列，每个阵列包含几千个元素。我现在想要获取范围[60,80]中的整体对象，而不触及每个集合中的上部60个对象，也不接触阵列中对象80之后的所有对象。

我正在考虑某种组合的修改二进制搜索。我现在的想法是类似如下（注意，这并非完全通过还认为，这只是一个想法）：

• GET对象中的每个阵列的60 - 范围的开头不能后作为每一个阵列将已经满足要求
• 使用这些对象作为每个阵列
• 从阵列中的一个在二进制搜索最大值，得到居中的对象（例如，30）
• 用二进制在所有其他数组中搜索，尝试在每个数组中找到对象，这会在之前，但尽可能靠近拾取的对象。
• 我们现在有3个对象，例如对象15,10和20.这些对象的总和将是45.因此，前面有42个对象，这比我们正在查找的范围的开始处更多（30）。我们继续在其中一个数组
• 的其余左半部分进行二进制搜索，如果我们取而代之的是总和小于我们正在寻找的范围的开始的值，我们继续在右边搜索。
• 在某些时候，我们会击中对象30.从那里开始，我们可以简单地从每个数组中逐个添加对象，并使用插入排序，直到我们达到范围长度。

我的问题是：

1. 是否有这种算法我这里所描述的任何名称？
2. 是否有其他算法或想法解决这个问题，可能更适合这个问题？

Thans提前任何想法或帮助！

Answer 1

人们通常把这个问题称为“多个排序数组联合中的选择”。 One of the questions in the sidebar是关于两个排序阵列的特例，this question是关于一般情况。综合答案中出现了几种基于比较的方法;他们或多或少必须确定每个单独阵列中的较低端点在哪里。你的二分查找答案是更好的方法之一;由于弗雷德里克森和约翰逊有一个渐近较快的算法，但它很复杂，而且对于小排名来说显然不是一个改进。