在超大有序整数向量中高效查找多值位置的方法

核心思路 #

因为两个向量都是有序无重复的，采用双指针归并式遍历是最优方案，时间复杂度为O(M + N)（M为w的规模，N为v的规模），远优于对w中每个元素执行二分查找的O(M log N)复杂度。

实现步骤 #

由于向量规模极大（v为10^10，w为1011），无法全量加载到内存，必须结合流式分块读取完成遍历：

• 1. 将v和w以有序格式存储在磁盘文件中（建议每个元素占一行，方便按行读取）。
• 2. 初始化两个文件流，分别指向v和w的起始位置，同时维护两个内存缓冲区（v_buf、w_buf），以及累计已读取的w元素总数（用于计算匹配位置）。
• 3. 分块读取v和w的数据到缓冲区，用双指针在缓冲区中进行匹配：
  • 若v_buf[i] == w_buf[j]：记录当前w的位置（total_w_read + j），同时移动两个指针。
  • 若v_buf[i] < w_buf[j]：移动v的指针；若指针到达缓冲区末尾，读取v的下一块数据到缓冲区，重置指针。
  • 若v_buf[i] > w_buf[j]：移动w的指针；若指针到达缓冲区末尾，更新累计已读取的w元素数，读取w的下一块数据到缓冲区，重置指针。
• 4. 当其中一个向量遍历完成时，终止流程。

C++关键实现细节 #

1. 20位数字的比较逻辑 #

20位数字超出64位整数范围，需用std::string存储，实现数值比较函数：

// 比较两个字符串表示的整数，a < b时返回true
bool isLess(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) {
        return a.size() < b.size();
    }
    return a < b; // 长度相同时，字典序等价于数值序
}

2. 流式分块读取示例 #

#include <fstream>
#include <vector>
#include <string>

// 从文件中读取最多max_count个元素到缓冲区
bool readBlock(std::ifstream& fs, std::vector<std::string>& buf, size_t max_count) {
    buf.clear();
    std::string line;
    while (buf.size() < max_count && std::getline(fs, line)) {
        buf.push_back(line);
    }
    return !buf.empty();
}

int main() {
    const size_t BUFFER_SIZE = 1000000; // 每个缓冲区存储1e6个元素，可根据内存调整
    std::ifstream v_file("v.txt");
    std::ifstream w_file("w.txt");
    std::vector<std::string> v_buf, w_buf;
    size_t total_w_read = 0;
    size_t i = 0, j = 0;

    // 初始化读取第一块数据
    readBlock(v_file, v_buf, BUFFER_SIZE);
    readBlock(w_file, w_buf, BUFFER_SIZE);

    while (!v_buf.empty() && !w_buf.empty()) {
        if (v_buf[i] == w_buf[j]) {
            // 输出匹配的w位置
            std::cout << "匹配位置：" << total_w_read + j << std::endl;
            i++;
            j++;
        } else if (isLess(v_buf[i], w_buf[j])) {
            i++;
            if (i == v_buf.size()) {
                // 读取v的下一块
                if (!readBlock(v_file, v_buf, BUFFER_SIZE)) {
                    v_buf.clear();
                }
                i = 0;
            }
        } else {
            j++;
            if (j == w_buf.size()) {
                // 更新已读取的w总数，读取下一块
                total_w_read += w_buf.size();
                if (!readBlock(w_file, w_buf, BUFFER_SIZE)) {
                    w_buf.clear();
                }
                j = 0;
            }
        }
    }

    return 0;
}

复杂度对比 #

• 二分查找方案：O(M log N) = 10^11 × log₂(10^10) ≈ 3.3×10^12次操作
• 双指针方案：O(M + N) = 10^11 + 10^10 = 1.1×10^11次操作，复杂度降低一个数量级以上

注意事项 #

• 必须保证v和w的文件是严格按数值从小到大排序且无重复元素，否则双指针逻辑会失效。
• 缓冲区大小可根据可用内存调整，更大的缓冲区能减少磁盘IO次数，提升整体效率。
• 需添加文件读取失败、空文件等异常情况的处理逻辑，保证程序鲁棒性。

内容的提问来源于stack exchange，提问作者Adam