下界上界给出相同的结果

Question

我试图在排序数组中找到最接近的值，但 upper_bound 和 lower_bound 都给出了最高值。

float abc[] = {1,3,4,5,6,7,8,9};

float *a  = lower_bound(abc, abc+8, 3.2);
cout<< *a;

return 0;

Answer 1

*a 在这两种情况下都是 4，因为 a 指向的值将是 3.2 如果正确插入到容器中。

如果传递的值不存在于容器中，

lower_bound 和 upper_bound 将 return 相同的迭代器，这里就是这种情况。

由 lower_bound 编辑的迭代器 return 被定义为传递的元素在容器中可以驻留的最低位置，higher_bound returns最高职位。他们不 return任何与数组中存在的最近的元素相关的事情。

为了找到最近的元素，你知道lower_bound的解引用结果大于或等于传递的值。之前的值（如果有）必须更小。您可以利用它来得出最接近的值。

Answer 2

由于数组中不存在值 3.2，因此 std::lower_bound 和 std::upper_bound 两种算法都将 return 相同的迭代器。

在这种情况下，您应该考虑使用前一个迭代器。

这是一个演示程序。

#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdlib>

int main() 
{
    float abc[] = { 1, 3, 4, 5, 6, 7, 8, 9 };
    float value = 3.2f;

    auto it = std::lower_bound( std::begin( abc ), std::end( abc ), value );

    auto closest = it;

    if ( it == std::end( abc ) )
    {
        closest = std::prev( it );
    }
    else if ( it != std::begin( abc ) )
    {
        closest = std::min( std::prev( it ), it, 
                            [&value]( const auto &p1, const auto &p2 )
                            {
                                return abs( value - *p1 ) < abs( value - *p2 );
                            } );
    }

    std::cout << *closest << " at position " << std::distance( std::begin( abc ), closest ) << std::endl;
    return 0;
}

它的输出是

3 at position 1

下界上界给出相同的结果

lower bound upper bound giving same results

c++

arrays

sorting

algorithm

lower-bound