c++ - 有效找到两个​​ vector 中最接近的对？

Question

给定两个类型为double的排序后的向量，其中向量的大小可能不同，我想生成一个成对的列表，两个向量中每个向量中的一个元素，其中一对元素之间的差异最小，并且没有两个对共享一个元素。向量都很大，必须在很短的时间内完成任务。
我尝试使用二进制搜索(请参见下文)，终止于相邻元素的比较以确定“最接近”的匹配，但是效率不足以在所需的时间范围内完成任务。
插值搜索需要花费同样长的时间。在某些算法中使用std::lower_bound()可以极大地加快代码的速度，但是它不会考虑元素小于搜索值的情况。
有没有很好的方法可以做到这一点？

double binarySearch(vector<double> vec, double val) {
       int left = 0; 
       int right = vec.size();
    
       while (left <= right) {
              int mid = (left+right)/2;

              if (vec[mid] == val)
                  return mid;
              else if (vec[mid] < val)
                       left = mid + 1;
              else 
                       right = mid - 1;
       }

       return minimum(vec[mid], vec[mid+1], vec[mid-1]);
}

Answer 1

希望这是什么意思:

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

template<class T>
std::vector<std::pair<T, T>> getClosestPairs(std::vector<T> v1, std::vector<T> v2) {
    std::vector<std::pair<T, T>> vPair;
    std::pair<size_t, size_t> indexs;
    std::pair<T, T> close;

    size_t i = 0, j = 0;
    T minDiff = std::numeric_limits<T>::max();

    while(v1.size() != 0 && v2.size() != 0) {
        while(i < v1.size() && j < v2.size()) {
            T diff = v1[i] < v2[j] ? v2[j] - v1[i] : v1[i] - v2[j];
            if(diff < minDiff) {
                minDiff = diff;
                // save index to delete them
                indexs = {i, j};
                // save the closest pair
                close = {v1[i], v2[j]};
            } else { // reached to min no need to move on res the cells
                break;
            }

            // Move the smaller vector's index forward
            if(v1[i] < v2[j]) {
                i++;
            } else {
                j++;
            }
        }
        vPair.push_back(close);
        v1.erase(v1.begin() + indexs.first);
        v2.erase(v2.begin() + indexs.second);
        i = j = 0;
        minDiff = std::numeric_limits<T>::max();
    }
    return vPair;
}
int main() {
    std::vector<double> v1 = {1, 4, 5, 7, 8, 13, 49};
    std::vector<double> v2 = {7, 10, 11, 15, 40};
    std::vector<std::pair<double, double>> result = getClosestPairs(v1, v2);
    for(auto [a, b] : result) std::cout << a << ',' << b << '\n';
}

输出:

7,7
8,10
13,11
5,15
49,40