我有许多包含排序数据的数组。我需要在这个数组中执行二进制搜索。如果此数组中的键范围不相交，则可以按范围对数组进行排序，然后像对单个数组一样执行二进制搜索。但就我而言，此数组中的键范围可以重叠。在这种情况下只能进行过滤排除一部分数组，然后对另一部分进行排序。 在我的例子中，大多数数组不重叠，因此过滤在大多数情况下只会返回一个数组，但错误数据仍有可能破坏性能。
在这种情况下是否可以使用更好的算法？可以稍微修改数组，添加一些元数据或指向其他数组的链接。
更新 该阵列是由磁盘存储支持的数据页。我为此使用内存映射文件。我可以非常快速地对页面内的数据进行排序，因为此过程不涉及复制。但是要合并两个页面，我需要在页面之间复制大量数据。 我有非常大的数据量，TB!但是每页只有8Mb，所以可以快速搜索。不时将新页面添加到存储中。 Pages 包含时间序列数据，因此它已经部分排序，并且新数组在大多数情况下不会与旧数据重叠。
最佳答案
If key ranges in this arrays were disjoint it will be possible to sort arrays by range and then perform binary search as with single array. But in my case, key-ranges in this arrays can overlap.
您仍然可以对它们进行排序。您可以使用 interval tree 而不是天真地按边界过滤所有数组。存储它们并以对数时间检索要搜索的数组。由于您有很多数组并且它们很少相互重叠，因此这应该会显着提高性能。
关于algorithm - 在许多排序数组中进行二进制搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19117802/