Reputation: 6655
I have a vector
of double
s. I wish to find both:
x
.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:
0
)Upvotes: 6
Views: 5383
Reputation:
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
Upvotes: 1
Reputation: 24936
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";
}
Upvotes: 5
Reputation: 310930
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.
Upvotes: 0
Reputation: 9321
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";
}
Upvotes: 2
Reputation: 9232
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.
Upvotes: 1
Reputation: 51
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
Upvotes: 2
Reputation: 63190
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.
Upvotes: 2