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.

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