Find the first element strictly less than a key in a vector sorted in descending order

Question

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.

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.

For instance:

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

My key is : 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!

Thanks

Answer 1

You can use the standard algorithm std::upper_bound with the functional object std::greater.

Here is an example how it can be done.

#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;
}

The program output is

9