在按降序排序的向量中找到严格小于键的第一个元素 [英] Find the first element strictly less than a key in a vector sorted in descending order

问题描述

我知道可以使用find_if（）STL-Algorithm函数来完成此任务，如下所示：

I understand that this task can be accomplished using the find_if() STL-Algorithm function as follows:

long long int k; //k = key
scanf("%lld",&k);
auto it = find_if(begin(v),end(v),[k](auto e){return e<k;});

但是我要求在对数时间内获得结果。由于向量已经按照降序排序，因此我想使用二进制搜索方法。

However I require the result to be obtained in logarithmic time. Since the vector is already sorted in descending order I'd like to use a binary search approach.

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

I understand the STL Algorithm function lower_bound and upper_bound guarantee a logarithmic complexity. However I'm unable to figure out how to use these functions to obtain the first element less than a key as opposed to the first element greater than or equal to a key.

例如：

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

Suppose my vector contents are: 21 9 8 7 6 4

我的关键是： 10

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

I would want the output to be 9, since its the first element in a left to right scan of the vector that is less than 10.

在这方面的任何帮助都将非常有帮助！

Any help in this regard would be very helpful!

谢谢

推荐答案

您可以对功能对象 std :: greater使用标准算法 std :: upper_bound 。

You can use the standard algorithm std::upper_bound with the functional object 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

这篇关于在按降序排序的向量中找到严格小于键的第一个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！