要执行 upper_bound 的反向操作,我需要做哪些更改?

What is the change I need to make to perform reverse of upper_bound?

感觉c++ stl中的lower_bound不是upper_bound函数的对立面。默认情况下,在非递减数组中,如果我使用 upper_bound 并且如果找到元素并且它不是排序数组中的最后一个元素,则给出下一个元素>传递的元素并且如果元素是然后最后一个元素或未找到,然后 end() 迭代器 returned。可以使用以下 C++ 代码对此进行测试。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int
main ()
{
  vector<int> arr{-973, -808, -550, 301, 414, 897};
  auto p = upper_bound (arr.begin (), arr.end (), 301);
  if (p != arr.end ())
    cout << *p << endl;
  else
    cout << "end" << endl;
  return 0;
}
// Output: 414

但现在我需要相反的东西。我需要 returned 匹配元素中较小的元素。在上面的例子中,如果我传递 301,那么,我想在 return 中得到 -550。目前,我正在使用以下代码,它似乎适用于给定的示例,但我不确定它是否是正确的代码,或者我需要使用二进制搜索手动实现它。

auto p = upper_bound(arr.rbegin(), arr.rend(), 301, greater<int>());

PS。为此,我正在使用 if (p != arr.rend ())

std::lower_bound 就是你想要的。 lower_bound returns 等于或大于所提供输入的第一个元素。知道这一点,如果你这样做

auto p = lower_bound(arr.begin (), arr.end (), 301);

然后 p 将在 301,从中减去 1 将得到元素 -550。因此,您只需要在执行 p != arr.begin() 的减法之前检查一下。如果是,则减法将起作用。如果不是,则没有元素少于传递给 lower_bound 的输入。这给你类似

的东西
auto p = lower_bound(arr.begin (), arr.end (), input_value);
if (p == arr.begin())
    std::cout << "no element found less than " << input_value;
else
    std::cout << "first element less than " << input_value << " is " << *std::prev(p);