C ++ эффективный поиск первого ближайшего подходящего значения в векторе?

Question

Учитывая несортированный вектор {6.0, 3.02, 4.2, 5.3} и заданное пороговое значение 0,1, как я могу эффективно найти первое совпадение со значением 3 (например) в пределах данного порогового значения в C ++?Моя текущая реализация выглядит следующим образом, но имеет сложность O (n).Я хочу улучшить это до O (log n), если это возможно.Большое спасибо заранее

std::vector<double> array = {6.0, 3.02, 4.2, 5.3};  
double val = 3 // the to be found value within the array above
double thresh = 0.1; // max threshold of the matching value
double found; // the matching value
for (int i = 0; i < array.size(); i++){
    if ( abs(array[i] - val) < thresh){
        found = array[i];
    }
}

Выход должен быть 3,02, поскольку это первое наиболее близкое совпадение с 3 в данном массиве в допустимом пороговом значении 0,1

РЕДАКТИРОВАТЬ: Если я могу себе позволитьсортировка вектора заранее, как я могу повторно реализовать вышеупомянутый поиск, чтобы быть O (log n)?Спасибо

Answer 1

Я думаю, что это невозможно.Лучшее, что вы можете улучшить в отсортированном массиве - это O (log (n)) с использованием бинарного поиска.Но в несортированном массиве вы в конечном итоге должны пройти через все элементы массива, а это O (n)

Answer 2

Как ни печально для других, вы не можете сделать лучше, чем поиск O (n) без сортировки массива.

Если мы сначала отсортируем массив, мы можем выполнить бинарный поиск и принять новую стратегию.

Нам нужно выяснить, какое из значений является первым в массиве, которое удовлетворяет (array [pos]> = (value - threshold)).Если мы можем найти такое значение, то мы проверяем, находится ли оно внутри диапазона [значение - порог, значение + порог].Если это так, мы возвращаем его, в противном случае мы этого не делаем.

Ниже приведен порядок реализации сортировки с использованием C ++.

#include <vector>
#include <algorithm>
#include <math.h>
#include <limits>
#include <iostream>
#include <iterator>

double binarySearch(std::vector<double>& array, const double value, const double threshold) 
{
    // I assume here that the array is sorted ...
    // If I cannot find it, I will return infinity (:

    double returnValue = std::numeric_limits<double>::infinity();

    std::vector<double>::iterator it = std::lower_bound(array.begin(), array.end(), value - threshold);

    if(it != array.end() ) 
    {
        if(fabs(*it - value) <= threshold ) returnValue = *it;
    }

    return returnValue;
}



int main() 
{
    std::vector<double> array = {6.0, 3.02, 4.2, 5.3};    
    double val = 3.0;
    double threshold = 0.1;

    // Sorting the array
    std::sort(array.begin(), array.end() );
    double res = binarySearch(array, val, threshold);

    if(res != std::numeric_limits<double>::infinity() )
    {
        std::cout << res << std::endl;
    }
    else std::cout << "Desired value not found" << std::endl;

    return 0;
}

Answer 3

Вы выполняете линейный поиск, который определенно равен O(n).Однако это, к сожалению, самый быстрый алгоритм поиска для несортированного массива / вектора.

Поэтому, чтобы получить что-то быстрее, вам нужно сначала отсортировать вектор. Сделайте это заранее, один раз, или ваш результирующий код будет на самом деле медленнее, чем линейный поиск. std::sort() достаточно эффективен - хотя есть несколько более быстрых алгоритмов сортировки, если вы захотите найти один.Убедитесь, что вы сохраняете отсортированный вектор, либо на месте, либо в новой переменной, в зависимости от ваших потребностей. Вы не хотите сортировать данные более одного раза.

Затем вы можете использовать алгоритм двоичного поиска, чтобы найти значение.std::lower_bound или std::upper_bound, вероятно, подойдет вашим потребностям (спасибо Эрику за эту заметку).В противном случае, если вы используете стандартный бинарный поиск, даже если точное совпадение не найдено, это приведет вас к тому, что вы смотрите на два или три значения, одно из которых определенно соответствует вашему.

Теперь, как указал Эрик в комментариях, сортировка обходится дороже, чем линейный поиск, поэтому, если вы ищете только этот набор данных один раз , у вас уже есть наиболее эффективный подход.

---

РЕДАКТИРОВАТЬ: В комментариях ОП описал необходимость иногда добавлять новые данные в вектор.Это довольно простая проблема, которую нужно решить: просто используйте двоичный поиск, чтобы найти, где новое значение принадлежит в векторе sorted , и вставьте его туда.