lower_bound() 给出意想不到的结果

Question

我写了一段代码，我需要从平方数序列中找到 lower_bound。但是下界给我 upper_bound.

的结果

这是我的代码和编译器 link: http://cpp.sh/3cppb

// Example program
#include <iostream>
#include <string>
#include <algorithm>

int main()
{
   std::vector<int> v{ 1, 4, 9, 16, 25 }; // all the square numbers
   
   int x = std::lower_bound(v.begin(), v.end(), 5) - v.begin() ;
   
   std:: cout<<"Postion "<<x<< "  value  "<<v[x] <<std::endl; //getting output for upperbound
   
}

输出：

Postion 2  value  9

预期输出

Postion 1  value  4

Answer 1

std::lower_bound returns 指向大于或等于目标值的第一个元素的迭代器：

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

由于9是第一个大于或等于5的值（当然更大），结果完全正确。

如果您尝试查找已在 v 中的元素，例如 9，那么您会得到 std::lower_bound 和 std::upper_bound 的不同结果：

std::distance(begin(v), std::lower_bound(begin(v), end(v), 9)); // 2
std::distance(begin(v), std::upper_bound(begin(v), end(v), 9)); // 3

Answer 2

std::lower_bound 工作正常。函数 return 是第一个不小于所提供值的元素。由于 9 是第一个不小于 5 的值，因此您将获得该元素。

在这种情况下，

std::upper_bound 将 return 与第一个大于指定值的元素 return 相同的元素。你会看到不同的地方是像

这样的情况

std::vector data = {4,4,4};
auto low = std::lower_bound(data.begin(), data.end(), 4);
auto high = std::upper_bound(data.begin(), data.end(), 4);

在这种情况下，low 将是 begin()，因为 4 不小于 4，而 high 将是 end()，因为没有大于 4 的元素矢量。

Answer 3

来自标准的引用，[lower.bound]：

template<class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

Returns: The furthermost iterator i in the range [first,last] such that for every iterator j in the range [first,i) the following corresponding conditions hold: *j < value.

lower_bound() 给出意想不到的结果

lower_bound() giving unexpected result

c++

stl

runtime-error

lower-bound