найти наиболее похожее значение между двумя векторами в C ++

Question

У меня есть два отсортированных вектора, и я хочу найти индекс значения в vector1, которое имеет наименьшую разницу (расстояние) от другого значения в vector2.Однако мой следующий код выполняет свою работу, потому что векторы, которые я использую, всегда сортируются, я чувствую, что в большинстве случаев есть еще один более эффективный способ сделать то же самое.Любые гиды?Заранее спасибо.

#include<iostream>
#include<cmath>
#include<vector>
#include<limits>
std::vector<float> v1{2,3,6,7,9};
std::vector<float> v2{4,6.2,10};
int main(int argc, const char * argv[]) 
{    
    float mn=std::numeric_limits<float>::infinity();
    float difference;
    int index;
    for(int i=0; i<v1.size(); i++){
        for(int j=0; j<v2.size(); j++){
            difference = abs(v1[i]-v2[j]);
            if(difference < mn){
                mn= difference;
                index = i;
            }
        }
    }
    std::cout<< index; 
    // 2 is the wanted index because |6-6.2| is the smallest distance between the 2 vectors 
    return 0;
}

Answer 1

Действительно, есть более быстрый путь.Вам нужно только сравнить элементы в v1 с элементами в v2, которые меньше или равны, или первым, который больше.По сути, идея состоит в том, чтобы иметь два итератора, i и j, и продвигать j, если v2[j] < v1[i], в противном случае продвигать i.Вот возможная реализация:

for (int i = 0, j = 0; i < v1.size(); i++) {
    while (true) {
        difference = std::abs(v1[i] - v2[j]);
        if (difference < mn) {
            mn = difference;
            index = i;
        }

        // Try the next item in v1 if the current item in v2 is bigger.
        if (v2[j] > v1[i])
              break;

        // Otherwise, try the next item in v2, unless we are at the last item.
        if (j + 1 < v2.size())
                j++;
        else
                break;
    }
}

Хотя он по-прежнему выглядит как двойной цикл, он вычисляет различия только самое большее v1.size() + v2.size() раз вместо v1.size() * v2.size() раз.