python - 当两个数组都已排序时，更快的搜索排序方法

Question

numpy.searchsorted(a, v, ...) 基本上找到排序数组a中第一个元素的索引大于或等于 v 中的元素。我认为这比不利用 a 已排序事实的方法更快。

现在如果 v 也已排序怎么办？当然应该可以利用这些知识来使算法更快？ (也许我错了，searchsorted 的设计使这变得无关紧要；如果是这样，请原谅我的问题。)

所以问题是:对于 a 和 来说，执行与 searchsorted(a, v) 相同的最快方法是什么v 已排序？

Answer 1

当 a 和 v 大小大致相同时，最好的算法在于合并两个数组(请参阅: merge algorithm )(请注意，您只需要索引而不是输出合并数组)。这可以在线性时间(即O(n+M))内完成，而不是准线性O(n log M)时间。

否则问题可以在O(n log log M)时间而不是O(n log n)时间内解决。仅当 a 很大时，这才有意义，因为 log M 已经相当小，并且应该小心算法复杂性中的隐藏常量。该算法的实现并不简单。想法如下:

• 选择 v 的中间值 v[k] 并将 v 虚拟地分成两部分(左右部分)
• 对 a 中的 v[k] 执行二分查找，以获取其位置 p
• 现在我们可以确定v左侧的项位于a[:p+1]中，右侧的部分位于中a[p:](在相等的情况下可以排除一侧，但为了简单起见，将其放在一边)
• 通过调用 search(a[:p+1], v[:k]) 和 search(a[p:], v[k+1: ])

请注意，对于第二种算法，如果v包含i多个相同的值，那么您可以将找到的位置复制i次并找到a 中更严格的下限/上限，以避免退化情况可能导致更糟糕的复杂性。

由于 CPython 循环开销和 Numpy 函数调用之一，此实现需要使用 C/C++ 等 native 语言或 Cython 或可能使用 Numba 等 JIT 来实现。