CODEWITHSUNDEEP
c++searchvector
Ash
Ash

Reputation: 4728

Searching a std::vector for approximations of a value

I have a vector,

std::vector<float> v;

and a float value, x. The vector v contains x+epsilon, where epsilon is very small (yet greater than the machine epsilon), but it doesn't contain x. Is there a way, using the STL, to find the index of x+epsilon in the vector?

Something like:

int i = alternative_find(v.begin(), v.end(), x, gamma) - v.begin();

which will return the index of all the values in v which are in [x-gamma,x+gamma]? I could implement a binary search function (I'd like to avoid linear time complexity), but I'd really like to know if it could be done in an easier way.

Upvotes: 0

Views: 963

Answers (3)

Tony Delroy
Tony Delroy

Reputation: 106246

If you're talking about binary search then obvious the vector's pre-sorted, which means you want to find the first element above x-gamma, then if you actually want to use the values it's fastest to increment further while they're in range. Check out lower_bound: http://en.cppreference.com/w/cpp/algorithm/lower_bound

If you just want to find the first and last, an alternative is to use upper_bound to binary search to its position, but that's likely slower than incrementing if there are a lot of elements and only a few match.

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254741

In C++11:

std::find_if(v.begin(), v.end(),
    [x,gamma](float f){return f >= x-gamma && f <= x+gamma;})

Historically, you'd have to write your own predicate, and it would probably be simpler to use a regular for loop.

(Although, regarding your last sentence, if the vector is or can be sorted, then you can do a binary search with lower_bound and upper_bound as described in other answers).

Upvotes: 1

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385385

Find the std::lower_bound, then the std::upper_bound, and you'll have your range.

From an iterator, you can obtain an index using std::distance (though stick with the iterator if you can!).

This assumes your data is sorted, but since you talk about binary searches that seems like a sensible assumption.

If it's not then you're going to have to examine every element anyway, in which case any approach is basically as good as another.

Upvotes: 2

Related Questions