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

Question

我知道这个任务可以使用find_if()STL-Algorithm函数完成,如下所示:

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.

在这方面的任何帮助将是非常有帮助的!

谢谢

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