c++ minimum value of vector greater than another value

Question

I have a vector of doubles. I wish to find both:

• The minimum value in the vector that is greater than (or equal to) a value x.
• The maximum value in the vector that is less than (or equal to) a value x.

E.g. If I have a vector:

std::vector<double> vec = {0, 1.0, 3.0, 4.0, 5.0};

and a value

x = 2.6;

I wish to find 1.0 and 3.0.

What is the most efficient way of doing this?

I have something like:

double x1, x2; // But these need to be initialised!!!
double x = 2.6;
for (i = 0; i < vec.size(); ++i)
{
  if (vec[i] >= x && vec[i] < x2)
       x2 = vec[i];
  if (vec[i] <= x && vec[i] > x1)
       x1 = vec[i];
}

But how can I initialise x1 and x2? I could make x2 the maximum of the vector and x1 the minimum, but this requires an initial pass through the data. Is there any way to do this more efficiently?

EDIT:

A couple of assumptions I think I can/cannot make about the data:

• There are no negatives (i.e. the minimum possible number would be 0)
• It is not necessarily sorted.

Thickening

Is the initial vector sorted, as in your example? – Columbarium

no, it wont be possible to assume it is sorted. – Thickening

You don't need any assumptions on the vector, and you can get away with a single pass (implicit or explicit) :) – Hole

@Hole if it is sorted you don't even need a single pass, just a binary search so it's O(ln N). Anyway, this is not the case... – Columbarium

@Columbarium yes in that case you could just use std::lower_bound to find one of the indices and find the other one in constant time from that. – Hole

Answer 1

You can use std::lower_bound :

#include <iterator>
#include <algorithm>

template<class ForwardIt, class T>
std::pair<ForwardIt, ForwardIt> hilo(ForwardIt first, ForwardIt last, T const &value)
{
    if (first != last)
    {
        auto lb = std::lower_bound(first, last, value);
        auto prelbd = std::distance(first, lb) - 1;
        if (lb == last) return{ std::next(first, prelbd), last };
        if (!(value < *lb)) return{ lb, lb };
        if (lb == first)  return{ last, first };
        return{ std::next(first, prelbd), lb };
    }
    return{ last, last };
}

Which can be used like:

std::vector<double> vec = { -1.0, -1.0, 0.0, 1.0, 3.0, 3.0, 3.0, 3.0, 4.0, 5.0, 5.0 };
// if not ordered
//std::sort(vec.begin(), vec.end());
double x = 5.0;
auto b = hilo(vec.begin(), vec.end(), x);
if (b.first != vec.end())
{
  std::cout << "First index: " << std::distance(vec.begin(), b.first) 
    << "(value " << *b.first << ")\n";
}
if (b.second != vec.end())
{
  std::cout << "Second index: " << std::distance(vec.begin(), b.second) 
    << "(value " << *b.second << ")\n";
}

Tentacle

std::upper_bound does not satisfy the condition "(or equal to)". – Weissman

Answer 2

To initialize the x1 and x2 to min and max of the vector, I would imagine you have no choice but to pass through it, unless you called std::sort on the vector first, and ordered in ascending or descending order, then picked the head/tail of the list, depending on your ordering, to initialize both values.

You can also use std::min_element to get the min value out of a containter, or std::max_element to find the max element in a container.

Sadducee

Answer 3

If you want to avoid an extra pass across the whole vector, you could always pick up the maximum possible value for the type you are using (in this case, double). STL gives you a way to do this, see e.g. here:

http://www.cplusplus.com/reference/limits/numeric_limits/

For your case, try something like:

#include <limits>       // std::numeric_limits
.
.
.
double x1 = std::numeric_limits<double>::max();
double x2 = std::numeric_limits<double>::min();
.
.
.
// rest of your code

Nygaard

Answer 4

Use iterators:

auto maxBelowX = vec.end();
for (auto i = vec.begin(); i != vec.end(); ++i)
{
    if (*i <= x && (i == vec.end() || *i > maxBelowX)) {
        maxBelowX = i;
    }
}

if (maxBelowX == vec.end()) {
    std::cout << "There was no element <= x";
}

Exum

Is T = auto? And do you mean, maxBelowX = i? – Hole

thanks for the tip; but this is just semantics (and perhaps performance I dont know), but does not really answer the question – Thickening

How do you mean, just semantics? I think this is quite a nice alternative solution that goes outside your box :) – Hole

@Thickening you need a special value or an out-of-band boolean that says "there was no value in vec smaller than x". A special value (like std::numeric_limits or NaN) can interfere with the contents of the vector, but requires no additional storage. The separate boolean flag requires additional storage, but doesn't interfere with the input domain. The end() iterator is equivalent to this separate flag. – Ban

@Thickening this is not just semantics, this is the answer and IMHO the best one provided so far. – Unroll

Answer 5

There is no need to pass through the vector to get the minimum and maximum value in the vector, since these are still not guaranteed to be less than or greater than x, respectively (consider the vector [1 2 3 4] for x = 5 - you can initialize x1 = 4 but after the loop you will mistakenly think that it is the smallest value >= 5).

It seems that what you would need is to initialize x1 and x2 to values that will unambiguously flag whether you found a minimum or maximum, where unambiguously means that you cannot mistake them for an actual value in the vector.

One suggestion, as given by Yannis Douros, is to use std::numeric_limits<double>::min() and std::numeric_limits<double>::max(). Or you can just go with

x1 = x - 1;
x2 = x + 1;

During the loop, x1 will get overwritten with the first value greater than x, so after the loop, all you need to do is check whether x1 >= x to know whether you found a minimum. If you have, its value will be x1.

Similarly, if x2 should be <= x, then the largest value smaller than x is x2, if on the other hand x2 > x (i.e. x2 is still x + 1) and you have not found a maximum.

Hole

Answer 6

This can be done using std::partition

std::vector<double> vec = {0, 1.0, 3.0, 4.0, 5.0};
double x = 2.6;
auto middle = std::partition(vec.begin(), vec.end(), 
    [x](const auto& v){return v < x;});
auto max_lt = *std::max_element(vec.begin(), middle); // = 1
auto min_gt = *std::min_element(middle, vec.end()); // = 3

Ephedrine

Answer 7

You may use the following approach

#include <iostream>
#include <vector>
#include <utility>

int main()
{
    std::vector<double> v = { 0, 1.0, 3.0, 4.0, 5.0 };
    double x = 2.6;

    auto minmax = std::make_pair( v.size(), v.size() );

    for ( std::vector<double>::size_type i = 0; i != v.size(); ++i )
    {
        if ( v[i] <= x && ( minmax.first == v.size() || v[minmax.first] < v[i] ) )
        {
            minmax.first = i;
        }
        else if ( x <= v[i] && ( minmax.second == v.size() || v[i] < v[minmax.second]  ) )
        {
            minmax.second = i;
        }
    }

    if ( minmax.first != v.size() )
    {
        std::cout << "The maximum value less than or equal to " << x
                  << " is " << v[minmax.first] << std::endl;
    }

    if ( minmax.second != v.size() )
    {
        std::cout << "The minimum value greater than or equal to " << x
                  << " is " << v[minmax.second] << std::endl;
    }

    return 0;
}

The program output is

The maximum value less than or equal to 2.6 is 1
The minimum value greater than or equal to 2.6 is 3

If the vector is sorted then you may use standard algorithm std::equal_range. For example

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
    std::vector<double> v = { 0, 1.0, 3.0, 4.0, 5.0 };
    double x = 2.6;

    auto minmax = std::equal_range( v.begin(), v.end(), x );

    if ( minmax.first == minmax.second )
    {
        if ( minmax.first != v.begin() ) std::advance( minmax.first, -1 );
        else minmax.first = v.end();
    }
    else
    {
        std::advance( minmax.second, - 1 ); 
    }


    if ( minmax.first != v.end() )
    {
        std::cout << "The maximum value less than or equal to " << x
                  << " is " << *minmax.first << std::endl;
    }

    if ( minmax.second != v.end() )
    {
        std::cout << "The minimum value greater than or equal to " << x
                  << " is " << *minmax.second << std::endl;
    }

    return 0;
}

The program output will be the same as shown above.

Postpositive