在大向量中查找多个值位置

Question

我有两个非常大的整数 v 和 w 有序向量。查找具有 v 中的值的 w 条目的位置的最有效方法是什么？我希望有比对 v 中的每个数字进行二分搜索更有效的方法。（计划在 C++ 中实现它。）

编辑：根据请求，举个例子：如果 v={3, 10, 20} 和 w={2,3,5,11,15,20} 那么我需要找到位置 i=1 和 i=5 因为 w [1]=3 且 w[5]=20。现在想象 v 的大小为 10^10，w 的大小为 10^11。

Answer 1

这在线性时间内很容易完成。

跟踪

w

和

v

中的当前索引。对于

w

中的每个索引，迭代

v

直到找到更大或相等的项目。如果相等，则发出索引。

//emits the indecies of items in A that are also in B
template<typename AIter, typename BIter, typename DIter>
DIter set_union_indecies(AIter a_first, AIter a_last, BIter b_first, BIter b_last, DIter dest) {
    unsigned index = 0;
    while (a_first != a_last) {
        // find the next item in B thats at least as big as the current item in A
        while(b_first != b_last && *b_first < *a_first)
            ++b_first;
        // if they're the same, then emit the index
        if (!(*a_first < *b_first))
            *dest++ = index;
        // check next value in A
        ++index;
        ++a_first;
    }
    return dest;
}

https://coliru.stacked-crooked.com/a/74636060f19e7e42

只要它们的大小相当相似，那就太好了。如果它们的大小相差很大，那么您将需要更多二进制搜索联合的东西。