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 could do a search in your vector for your value (which would tell you where your value would be if it were in the vector) and then return the value before and after that location. So searching for 45 would tell you it should be at index=1 and then you would return 0 and 1 (depending on your implementation of the search, you'll either get the index of the smaller value or the index of the larger value, but this is easy to check with a couple boundary conditions). This should be able to run in O(log n) where n is the number of elements in your vector.

Answer 2

What if (in your case) d is less than the first element or more than the last? And how to deal with negative values? By the way: guaranteeing that your "d" lives between the first and the last value of your vector you can do like that:

// Your initializations
std::vector<double>::const_iterator sit = f.begin();
double upper, lower;

Here is the rest:

while ( *sit < d )         // if the element is still less than your d
    ++sit;                 // increase your iterator

upper = *sit;              // here you get the upper value
lower = *(--sit);          // and here your lower

Elegant enough? :/

Answer 3

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;
}

Answer 4

You could simply use a binary search, which will run in O(log(n)).

Here is a Lua snippet (I don't have time to do it in C++, sorry) which does what you want, except for limit conditions (that you did not define anyway) :

function search(value, list, first, last)
    if not first then first = 1; last = #list end

    if last - first < 2 then
     return list[first], list[last]
    end

    local median = math.ceil(first + (last - first)/2)

    if list[median] > value then
     return search(value, list, first, median)
    else
     return search(value, list, median, last)
    end
end

local list = {1,10,100,1000}

print(search(arg[1] + 0, list))

It takes the value to search from the command line :

$ lua search.lua 10 # didn't know what to do in this case
10  100
$ lua search.lua 101
100 1000
$ lua search.lua 99
10  100

Answer 5

If you have the ability to use some other data structure (not a vector), I'd suggest a B-tree. If you data is unchanging, I believe you can retrieve the result in constant time (logarithmic time at the worst).

Answer 6

I would write something like this, didn't test if this compiles, but you get the idea:

template <typename Iterator>
std::pair<Iterator, Iterator> find_best_pair(Iterator first, Iterator last, const typename Iterator::value_type & val)
{
    std::pair<Iterator, Iterator> result(last, last);

    typename Iterator::difference_type size = std::distance(first, last);

    if (size == 2)
    {
        // if the container is of size 2, the answer is the two elements 
        result.first = first;
        result.first = first;
        ++result.first;
    }
    else
    {

        // must be of at lease size 3
        if (size > 2)
        {
            Iterator second = first;
            ++second;
            Iterator prev_last = last;
            --prev_last;
            Iterator it(std::lower_bound(second, last, val));

      if (it != last)
      {

                result.first = it;
                result.second = it;


                if (it != prev_last)
                {
                    // if this is not the previous last
                    // then the answer is (it, it + 1)
                    ++result.second;
                }
                else
                {
                    // if this the previous last
                    // then the answer is (it - 1, it)
                    --result.first;
                }

      }

        }

    }

    return result;


}

Answer 7

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 8

I'm going to post my own anser, and vote anyone up that helped me to reach it, since this is what I'll use in the end, and you've all helped me reach this conclusion. Comments are welcome.

std::pair<value_type, value_type> GetDivisions(const value_type& from) const
{
    if (m_divisions.empty())
        throw 0; // Can't help you if we're empty.

    std::vector<value_type>::const_iterator it = 
        std::lower_bound(m_divisions.begin(), m_divisions.end(), from);

    if (it == m_divisions.end())
        return std::make_pair(m_divisions.back(), m_divisions.back());
    else if (it == m_divisions.begin())
        return std::make_pair(m_divisions.front(), m_divisions.front());
    else
        return std::make_pair(*(it - 1), *(it));
}

Answer 9

I wrote up this little function, which seems to fit the more general case you wanted. I haven't tested it totally, but I did write a little test code (included).

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

template <class RandomAccessIt, class Container, class T>
std::pair<RandomAccessIt, RandomAccessIt> bracket_range(RandomAccessIt begin, RandomAccessIt end, Container& c, T val)
{
    typename Container::iterator first;
    typename Container::iterator second;

    first = std::find(begin, end, val);
    //Find the first value after this by iteration
    second = first;
    if (first == begin){ // Found the first element, so set this to end to indicate no lower values
 first = end;
    }
    else if (first != end && first != begin) --first; //Set this to the first value before the found one, if the value was found
    while (second != end && *second == val) ++second;
    return std::make_pair(first,second);
}

int main(int argc, _TCHAR* argv[])
{
    std::vector<int> values;
    std::pair<std::vector<int>::iterator, std::vector<int>::iterator> vals;

    for (int i = 1; i < 9; ++i) values.push_back(i);

    for (int i = 0; i < 10; ++i){
     vals = bracket_range(values.begin(), values.end(),values, i);
     if (vals.first == values.end() && vals.second == values.end()){ // Not found at all
      std::cout << i << " is not in the container." << std::endl;
     }
     else if (vals.first == values.end()){ // No value lower
      std::cout << i << ": " << "None Lower," << *(vals.second) << std::endl;
     }
     else if (vals.second == values.end()) { // No value higher
      std::cout << i << ": " << *(vals.first) << ", None Higher" << std::endl;
     }
     else{
  std::cout << i << ": " << *(vals.first) << "," << *(vals.second) << std::endl;
     }
    }
    return 0;
}