在按降序排列的向量中查找严格小于关键字的第一个元素。

Question

我了解可以使用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;});

然而我需要在对数时间内获得结果。由于向量已经按降序排序，我想使用二进制搜索方法。

我了解STL算法函数lower_bound和upper_bound保证具有对数复杂度。但是，我无法想出如何使用这些函数来获得小于关键字的第一个元素，而不是大于或等于关键字的第一个元素。

例如：

假设我的向量内容为：21 9 8 7 6 4

我的关键字是：10

我希望输出结果为9，因为它是从向量左到右扫描时第一个小于10的元素。

在这方面提供任何帮助将非常有用！

谢谢

- Varun Rao

---

基本上就是这个（https://dev59.com/1WrXa4cB1Zd3GeqPD-VI），但你需要将向后搜索改为向前搜索。 - NathanOliver

Answer 1

您可以使用标准算法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

- Vlad from Moscow