我知道可以使用 find_if() STL 算法函数完成此任务，如下所示:
long long int k; //k = key
scanf("%lld",&k);
auto it = find_if(begin(v),end(v),[k](auto e){return e<k;});
但是我要求在对数时间内得到结果。由于 vector 已经按降序排序，我想使用二进制搜索方法。
我了解 STL 算法函数 lower_bound 和 upper_bound 保证对数复杂度。但是，我无法弄清楚如何使用这些函数来获取小于键的第一个元素，而不是大于或等于键的第一个元素。
例如:
假设我的 vector 内容是:21 9 8 7 6 4
我的 key 是:10
我希望输出为 9，因为它是 vector 从左到右扫描中小于 10 的第一个元素。
在这方面的任何帮助都会非常有帮助!
谢谢
最佳答案
您可以将标准算法 std::upper_bound 与函数对象 std::greater 一起使用。
这是一个如何完成的示例。
#include <iostream>
#include <iterator>
#include <functional>
#include <algorithm>
int main()
{
int a[] = { 21, 9, 8, 7, 6, 4 };
int key = 10;
auto it = std::upper_bound(std::begin(a), std::end(a),
key, std::greater<int>());
if (it != std::end(a)) std::cout << *it << std::endl;
}
程序输出为
9
关于c++ - 在按降序排序的 vector 中查找严格小于某个键的第一个元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44179512/