CODEWITHSUNDEEP
c++searchvectorc++11std
eigen_enthused
eigen_enthused

Reputation: 535

Find index of value in Vector, nearest to the input

Is there an efficient method of finding the index of a value in a Vector, closest to a reference value?

Upvotes: 3

Views: 7264

Answers (2)

Andy Prowl
Andy Prowl

Reputation: 126552

Computationally, if the vector is not sorted, you can't expect anything less than O(n), which may or may not meet your expectation. If it doesn't, you should change the data structure. If it does, you could use std::min_element, this way:

#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
    int refElem = 42;
    std::vector<int> v{1, 5, 36, 50};
    auto i = min_element(begin(v), end(v), [=] (int x, int y)
    {
        return abs(x - refElem) < abs(y - refElem);
    });

    std::cout << std::distance(begin(v), i); // Prints 2
}

If the vector is sorted, on the other hand, you can use std::lower_bound() and std::upper_bound(), which have logarithmic complexity.

If you think complexity is an issue because of performance, do some measurements before deciding to change the data structure. Since vectors store their elements in a contiguous region of memory, a linear search resulting in high cache hit rate will often outperform a computationally more efficient algorithm on a data structure which allocates its element here and there in memory, resulting in frequent cache misses.

Upvotes: 10

Roman Nikitchenko
Roman Nikitchenko

Reputation: 13046

  1. Looks like linear search is your choice (at least for unsorted vector. It looks there is no point in sorting vector just for search.

  2. In general everything depends on what do you mean under 'closest'. This 'closest' should be probably implemented as unary predicate. Predicate should return value like 0 if elements are equal and some value that is the bigger the less close element is from reference.

  3. As I can see from <algorithm> most close algorithm to what you need is std::min_element but you need not only range parameters but also reference element (or predicate which determines 'how close' is your element to reference.

  4. Probably you can receive some benefit from checking if elements are equal and if so, breaking the loop.

Upvotes: 1

Related Questions