Find nearest points in a vector

Question

Given a sorted vector with a number of values, as in the following example:

std::vector<double> f;
f.pushback(10);
f.pushback(100);
f.pushback(1000);
f.pushback(10000);

I'm looking for the most elegant way to retrieve for any double d the two values that are immediately adjacent to it. For example, given the value "45", I'd like this to return "10" and "100".

I was looking at lower_bound and upper_bound, but they don't do what I want. Can you help?

EDIT: I've decided to post my own anser, as it is somewhat a composite of all the helpful answers that I got in this thread. I've voted up those answers which I thought were most helpful.

Thanks everyone,

Dave

Answer 1

You can grab both values (if they exist) in one call with equal_range(). It returns a std::pair of iterators, with first being the first location and second being the last location in which you could insert the value passed without violating ordering. To strictly meet your criteria, you'd have to decrement the iterator in first, after verifying that it wasn't equal to the vector's begin().

Answer 2

You can use STL's lower_bound to get want you want in a few lines of code. lower_bound uses binary search under the hood, so your runtime is O(log n).

double val = 45;
double lower, upper;
std::vector<double>::iterator it;
it = lower_bound(f.begin(), f.end(), val);
if (it == f.begin()) upper = *it; // no smaller value  than val in vector
else if (it == f.end()) lower = *(it-1); // no bigger value than val in vector
else {
    lower = *(it-1);
    upper = *it;
}