將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是關於一般情況。綜合答案中出現了幾種基於比較的方法;他們或多或少必須確定每個單獨陣列中的較低端點在哪裏。你的二分查找答案是更好的方法之一;由於弗雷德裏克森和約翰遜有一個漸近較快的算法，但它很複雜，而且對於小排名來說顯然不是一個改進。