Elegant way to find closest value in a vector from above

Question

I need a function that takes a vector (assumed to be sorted), and a value, and returns the closest number that's [edit] greater than less than or equal to that number, preferably using an algorithm from the STL. I have come up with a solution using std::lower_bound(), but it seems kludgy and ugly:

struct ClosestCmp {
    bool operator()(const int & x, const int & y) { return x > y; }
};

// vec is assumed to be sorted
int closest(const std::vector<int> & vec, int value)
{
    std::vector<int>::const_reverse_iterator cri =
        std::lower_bound(vec.rbegin(), vec.rend(), value, ClosestCmp());
    if (cri != vec.rend()) {
        return *cri;
    }
    return -1;
}

// ...
vec.push_back(1);
vec.push_back(2);
vec.push_back(4);
vec.push_back(5);
std::cout << closest(vec, 2) << "\n"; // Should ouput "2"
std::cout << closest(vec, 3) << "\n"; // Should ouput "2"
std::cout << closest(vec, 4) << "\n"; // Should ouput "4"

Can anyone suggest a way that's more elegant, maybe using an STL algorithm without needing a comparison function or a reverse iterator? I have looked in the STL, but haven't been able to find a better solution than this.

Solution 1

You can only use std::lower_bound and std::upper_bound with binary predicates that match the order of the container. So, you can't sort by < and then use a different binary predicate (say <= or >). So your "kludge" is actually the correct thing to do. The sorted vector in reverse is the ordering criteria you want to use to find the element less than or equal to the value. (Otherwise, if you were actually searching for the value greater than or equal to, you could just use std::lower_bound.)

Solution 2

For reminder:

• std::lower_bound: returns the first value that does not compare less
• std::upper_bound: returns the first value that compares strictly greater

From your description, std::lower_bound already looks like the perfect fit, what is wrong with:

int closest(std::vector<int> const& vec, int value) {
    auto const it = std::lower_bound(vec.begin(), vec.end(), value);
    if (it == vec.end()) { return -1; }

    return *it;
}

Which is used as:

int main() {
    std::vector<int> vec;
    vec.push_back(2);
    vec.push_back(4);

    std::cout << closest(vec, 2) << "\n";
    std::cout << closest(vec, 3) << "\n";
    std::cout << closest(vec, 4) << "\n";
}

Output:

2
4
4

Solution 3

Requires C++11:

template<typename InputIterator, typename ValueType>
InputIterator closest(InputIterator first, InputIterator last, ValueType value)
{
    return std::min_element(first, last, [&](ValueType x, ValueType y)
    {   
        return std::abs(x - value) < std::abs(y - value);
    });
}