STL "closest" method?

Question

I'm looking for an STL sort that returns the element "closest" to the target value if the exact value is not present in the container. It needs to be fast, so essentially I'm looking for a slightly modified binary search... I could write it, but it seems like something that should already exist...

Answer 1

Do you mean the lower_bound/upper_bound functions? These perform a binary search and return the closest element above the value you're looking for.

Clarification: The global versions of lower/upper_bound only work if the range is sorted, as they use some kind of binary search internally. (Obviously, the lower/upper_bound methods in std::map always work). You said in your question that you were looking for some kind of binary search, so I'll assume the range is sorted.

Also, Neither lower_bound nor upper_bound returns the closest member. If the value X you're looking for isn't a member of the range, they will both return the first element greater then X. Otherwise, lower_bound will return the first value equal to X, upper_boundwill return the last value equals X.

So to find the closest value, you'd have to

• call lower_bound
• if it returns the end of the range, all values are less then X. The last (i.e. the highest) element is the closest one
• it if returns the beginning of the range, all values are greater then X. The first (i.e. the lowest) element is the closest one
• if it returns an element in the middle of the range, check that element and the element before - the one that's closer to X is the one you're looking for

Answer 2

So you're looking for an element which has a minimal distance from some value k?

Use std::transform to transform each x to x-k. The use std::min_element with a comparison function which returns abs(l) < abs(r). Then add k back onto the result.

EDIT: Alternatively, you could just use std::min_element with a comparison function abs(l-k) < abs(r-k), and eliminate the std::transform.

EDIT2: This is good for unsorted containers. For sorted containers, you probably want nikie's answer.

Answer 3

If your data is not sorted, use std::min_element with a comparison functor that calculates your distance.

Answer 4

If the container is already sorted (as implied) you should be able to use std::upper_bound and the item directly before to figure out which is closest:

// Untested.
template <class Iter, class T>
Iter closest_value(Iter begin, Iter end, T value)
{
    Iter result = std::upper_bound(begin, end, value);
    if(result != begin)
    {
        Iter lower_result = result;
        --lower_result;
        if(result == end || ((value - *lower_result) < (*result - value)))
        {
            result = lower_result;
        }
    }

    return result;
}

If the container is not sorted, use min_element with a predicate as already suggested.