在C++中搜索双精度数组中的最近值？

Question

我在C++中有一个double值的排序数组.是否有一个STL函数将返回索引中的最近的数组中值与给定值的两倍？

例如,给定以下数组

double myarray[5] = { 1.0, 1.2, 1.4. 1.5, 1.9 };

函数调用

search(myarray, 1.6);

应该返回3,最接近1.6的元素的索引,而不是-1(或一些其他标志值),表示未找到值1.6.

Answer 1

也许std::lower_bound std::upper_bound会帮助你.

Answer 2

这是一个通用的解决方案std::lower_bound:

template <typename BidirectionalIterator, typename T>
BidirectionalIterator getClosest(BidirectionalIterator first, 
                                 BidirectionalIterator last, 
                                 const T & value)
{
    BidirectionalIterator before = std::lower_bound(first, last, value);

    if (before == first) return first;
    if (before == last)  return --last; // iterator must be bidirectional

    BidirectionalIterator after = before;
    --before;

    return (*after - value) < (value - *before) ? after : before;
}

您会注意到我使用了双向迭代器,这意味着该函数只能与可以递增和递减的迭代器一起使用.更好的实现只会强加Input Iterators概念,但对于这个问题,这应该足够好了.

既然你想要索引而不是迭代器,你可以编写一个小帮助函数:

template <typename BidirectionalIterator, typename T>
std::size_t getClosestIndex(BidirectionalIterator first, 
                            BidirectionalIterator last, 
                            const T & value)
{
    return std::distance(first, getClosest(first, last, value));
}

现在你最终得到这样的代码:

const int ARRAY_LENGTH = 5;
double myarray[ARRAY_LENGTH] = { 1.0, 1.2, 1.4. 1.5, 1.9 };

int getPositionOfLevel(double level)
{
    return getClosestIndex(myarray, myarray + ARRAY_LENGTH, level);
}

它给出了以下结果:

level | index
 0.1  |  0
 1.4  |  2
 1.6  |  3
 1.8  |  4
 2.0  |  4